最小生成树算法

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：Mar.11 2022

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

目录

有特定需要的内容直接跳转到相关章节查看即可。

正在加载目录...

最小生成树定义

    我们将连通赋权图中权值最小的生成树 (i.e. 生成树中所有边权值的和) 称为 最小生成树(Minimum Spanning Tree)。

Kruskal 算法

    Kruskal 算法 的大致思想是：从 `G` 中的最小边开始，进行避圈式扩张。算法的大致步骤是：

1. 选择边 `e_1`，使得其权值最小；
2. 若已经选定边 `e_1`, `e_2`, `…`, `e_k`，则从 `E–{e_1, e_2, …, e_k}` 中选择边 `e_{k+1}`，使得:
   1. `G[e_1, e_2, …, e_{k+1}]` 为无圈图;
   2. `e_{k+1}` 的权值 `w(e_{k+1})` 尽可能小
3. 当 (2) 不能进行时，停止。

    Kruskal 算法下面的性质，我们这里省去证明。

由 Kruskal 算法得到的任何生成树一定是最小生成树。

破圈法

    破圈法 与上述的 Kruskal 算法的思路相反，其求最小生成树的求解过程是：从赋权图 `G` 的任意圈开始，去掉该圈中权值最大的一条边，称为破圈。不断破圈，直到G中没有圈为止，最后剩下的 `G` 的子图为 `G` 的最小生成树。

Prim 算法

    Prim 算法 的基本思路是：对于连通赋权图 `G` 的任意一个顶点 `u`，选择与点 `u` 关联的且权值最小的边作为最小生成树的第一条边 `e_1`。然后在接下来的边 `e_2`, `e_3`, `…`, `e_{n-1}` 中，在与一条已经选取的边只有一个公共端点的所有边中，选取权值最小的边。

    上述算法的思路和我们 前面 使用 Dijkstra 算法求解最短路的思想非常相似。

根树

一些基本定义

    给定一棵树 `T`，如果每条边都有一个方向，称这种树为 有向树 (Directed Tree)，如上图所示。对于 `T` 的顶点 `v` 来说，以点 `v` 为终点的边数称为点 `v` 的 入度 (Indegree)，以点 `v` 为起点的边数称为点 `v` 的 出度 (Outdegree)。入度与出度之和称为点 `v` 的度。

    一棵非平凡的有向树 `T`，如果恰有一个顶点的入度为 `0`，而其余所有顶点的入度为 `1`，这样的的有向树称为 根树 (Rooted Tree). 其中入度为 `0` 的点称为 树根 (Root), 出度为 `0` 的点称为 树叶 (Leaf)，入度为 `1`，出度大于等于 `1` 的点称为 内点 (Internal Vertex)，又将内点和树根统称为 分支点 (Branch Vertex)。

    对于根树 `T`，顶点 `v` 到树根的距离称为点 `v` 的 层数 (Level)，所有顶点中的层数的最大者称为根树 `T` 的 树高 (Height)。

    对于根树 `T`，若规定了每层顶点的访问次序, 这样的根树称为 有序树。

    对于根树 `T`, 由点 `v` 及其 `v` 的后代导出的子图，称为根树的 子根树 (Sub-rooted Tree)。

    对于根树 `T`，若每个分支点至多 `m` 个儿子, 称该根树为 m 元根树 (m-ary Rooted Tree)。若每个分支点恰有 `m` 个儿子，称它为 完全 m 元树 (Complete m-ary Rooted Tree)。

    对于完全 `m` 元树 `T`，有如下性质：

在完全 `m` 元树 `T` 中, 若树叶数为 `t`，分支点数为 `i`，则：`[m(T)-1] \cdot i = t - 1`

    现在我们给出证明：一方面，由树的性质可得 `m(T) = (i+t)`；另一方面，由握手定理可得 `2 \cdot m(T) = t + m + (i-1)\cdot(m+1)` (咋来的？)。故由这两式相消即可得到结果。

最优二元树和霍夫曼编码

    设 `T` 是一棵二元树, 若对所有 `t` 片树叶赋权值 `w_i(1 \le i \le t)`，且权值为 `w_i` 的树叶层数为 `L(w_i)`，称：

`W(T)=\sum_{i=1}^{t}w_i \cdot L(w_i)`

为赋权二元树的 权 (Weight)，而在所有赋权为 `w_i` 的二元树中 `W(T)` 最小的二元树称为 最优二元树。

    现在我们来看 霍夫曼 (Huffman) 算法，有时也称为 霍夫曼 (Huffman) 编码：

1. 初始: 令 `S={w_1, w_2, …,w_i,…,w_j,…w_t}`
2. 从 `S` 中取出两个权值最小者 `w_i` 与 `w_j`, 画结点 `v_i`, 带权 `w_i`, 画结点 `v_j`, 带权 `w_j`, 画 `v_i` 与 `v_j` 的父亲`v`, 连接 `v_i` 与 `v`, 连接 `v_j` 与 `v`, 令 `v` 带权 `w_i + w_j`
3. 令 `S = (S−{w_i , w_j}) \cup {wi+wj}`
4. 判断 `S` 是否只含一个元素, 若是, 停止, 否则转(2)