第 9 讲 · 树、编码与生成树

树是连通且无圈的无向图。它恰好保留了连接所有顶点所需的最少边，因此既是层次结构的模型，也是很多图算法的骨架。

树有多组等价刻画

对 nn 个顶点的非平凡无向图，下面的条件互相关联：

  • 连通且无圈；
  • 任意两点之间恰有一条基本链；
  • 连通且边数为 n−1n-1；
  • 无圈且边数为 n−1n-1；
  • 每条边都是桥；
  • 加入任意一条新边都会产生唯一的圈。

做证明时选最贴近题设的一条。例如已知连通图有圈，就删掉圈中一条边，连通性不变；反复破圈，最终得到生成树。

有根树把无向结构变成层次

选定根并把边由父节点指向子节点，就得到有根树。根的入度为 0，其他顶点入度为 1；从根到顶点的路径长度是深度。课件进一步区分有序树、mm 叉树、满 mm 叉树、完美树和完全树。

二叉树的每个节点最多有左右两个孩子。三种遍历的差别只在访问根的时机：

  • 前序：根—左—右；
  • 中序：左—根—右；
  • 后序：左—右—根。

只有一种遍历序列通常不能唯一还原二叉树；前序配中序、或后序配中序，在节点互异时可以逐层确定根和左右子树。

前缀编码对应二叉树的叶子

若任何码字都不是另一码字的前缀，就能从左到右即时解码。令左边记 0、右边记 1，叶节点从根到叶的路径就是码字；内部节点不能当码字，否则它会成为后代码字的前缀。

若符号概率为 pip_i、码长为 lil_i，平均码长为：

L=∑ipili.L=\sum_i p_i l_i.

Huffman 算法每次合并权重最小的两个节点，把和重新放回候选集合，最终得到最小平均码长的前缀编码树。高概率符号自然靠近根，得到更短码字。熵 −∑ipilog⁡2pi-\sum_i p_i\log_2p_i 是平均码长的理论下界，不等于任意具体编码的长度。

生成树保留全部顶点

图 GG 的生成树是保留 GG 全部顶点的树形子图。nn 个顶点、mm 条边的连通图相对于某棵生成树有 n−1n-1 条树枝和 m−n+1m-n+1 条弦。

带权连通无向图的最小生成树（MST）让树边权之和最小：

  • Kruskal 按边权从小到大扫描，只加入不会形成圈的边；
  • Prim 从一个顶点集合出发，每次选连接已选集合与外部的最轻边；
  • 破圈法 每次从圈中删掉一条最重边，直到剩下树。

Kruskal 关心两个连通分量能否合并，Prim 关心当前割的最轻跨边；二者都依赖交换论证。MST 与最短路不同：前者最小化连接全部顶点的总边权，后者最小化一个源点到目标的路径权。

割集与基本圈互为两种观察角度

割集是删去后恰把连通图分成两部分、且不能再少删边的边集；单边割集就是桥。给定生成树 TT：

  • 删除一条树枝会把树分成两块，原图中跨越这两块的所有边构成一个基本割集；
  • 加入一条弦会产生唯一的圈，称为这条弦的基本圈。

任何圈和任何割集的公共边数必为偶数，因为沿圈出发并回到原侧，跨过两块之间边界的次数必须成对。这个结论把“圈空间”和“割空间”的关系直观地连接起来。

课件还把 MST 用于聚类：先构造样本完全图的最小生成树，再删除若干条最重边得到多个分量。它能保留局部相似连接，但结果高度依赖距离定义，也容易被桥接噪声影响。

评论