算法学习笔记（二）：最小生成树

最小生成树的定义

给定一个连通无向图 $G=(V,E)$ 和权重函数 $w:E rightarrow mathbb{R}$，我们希望找到图 $G$ 的一个生成树 $T$（它连接了所有的顶点）满足：$w(T)=sum_{(u,v)in T}w(u,v)$ 的值最小，那我们称 $T$ 为最小生成树。如下面连通图所示，其中加阴影的边构成一个最小生成树：

求解最小生成树

我们首先分析最小生成树问题可以采用动态规划方法求解。应用动态规划求解的问题需要包含两个基本特点：存在最优子结构与子问题重叠。

最优子结构：

最小生成树问题具备最优子结构。我们可以通过移除某条边 $(u,v)$ 从而得到两个子树 $T_1$ 与 $T_2$。实际上，$T_1$ 与 $T_2$ 分别是其对应子图 $G_1$ 与 $G_2$ 的最小生成树。因此，最小生成树问题具备最优子结构。

沿用算法导论的证明思想，我们可以采用“剪切-粘贴”方法证明：

• 因为 $T$ 是图 $G$ 的一个最小生成树，且有 $w(T)=w(u,v) + w(T_1) + w(T_2)$；
• 如果子图 $G_1$ 存在一个生成树 $T_1^{prime}$，有 $w(T_1^{prime}) < w(T_1)$；
• 那么我们就可以得到图 $G$ 一个新的生成树 $T^{prime}$： $w(T^{prime})=w(u,v) + w(T_1^{prime}) + w(T_2)$；
• 因此 $w(T)>w(T^{prime})$，这与 $T$ 是最小生成树矛盾，得证。

子问题重叠：

该问题存在子问题重叠。举个最简单的例子：我们可以通过更改不同边被移除的顺序，这样我们就会得到多个重叠的子问题。

基于上述分析，我们可以采用动态规划的方法去求解最小生成树问题。但实际上最小生成树问题具备一个更强大的特性，这使得我们可以使用复杂度更低的贪心算法去求解。

与动态规划类似，贪心算法也要求问题具备最优子结构，但其最具标识性的特点是：问题的局部最优解也是全局最优解。

我们描述一个定理，它可以帮助我们通过贪心选择来得到最小生成树（更完善严谨的数学描述与证明，需要参考算法导论，这里为方便理解仅做简单的描述）：

定理：给定图 $G=(V,E)$，$T$ 是图 $G$ 的最小生成树，令 $A subseteq V$，假设边 $(u,v)$ 连接着两个集合：$A$ 与 $V-A$，并且是集合 $V-A$ 中有着最小权重的边，那么边 $(u,v)$ 属于最小生成树中的边。

要证明上述定理，我们可以从假设最小生成树 $T$ 中不包含 $(u,v)$ 这条边出发，推导出矛盾。

以下图最小生成树 $T$ 为例，设橙色结点属于集合 $A$，白色结点属于 $V-A$。$u$ 与 $v$ 之间以虚线连接，注意 $(u,v)$ 就是我们在定理中描述的，它满足两个性质。在我们的假设中，它不属于最小生成树的边。首先，必定至少存在一条边横跨集合 $A$ 与 $V-A$（因为两个集合之间连接起来，肯定需要一些过渡边），我们可以假设这条边就是 $(x,y)$。此时如果我们把 $(x,y)$ 从 $T$ 的边中给踢出去，而把 $(u,v)$ 加进来，就会得到一颗新的生成树 $T^{prime}=T-{(x,y) } cup {(u,v) }$，由于 $w(T^{prime}) < w(T)$ 与 $T$ 是最小生成树矛盾，得证。

Kruskal 算法与 Prim 算法

上述的分析为我们指明了贪心选择的关键点在于：如果选择 $(u,v)$，它要横跨集合 $A$ 与 $V-A$，并且是集合 $V-A$ 中权重最小的边。基于这种通用算法的思想，Kruskal 与 Prim 是具体的实现。

Kruskal 算法：

Kruskal 算法的过程如下所示：

1. 将集合 $A$ 初始化为一个空集，并且创建了 $|V|$ 个集合，每个集合仅包含它自身一个结点；
2. 按权重从低到高对边做排序，并存储在链表 $G.E$ 中；
3. 每次迭代从 $G.E$ 取出边 $(u,v)$，如果这条边是横跨集合 $A$ 与 $V-A$（对应判断条件 FIND-SET(u) ≠ FIND-SET(v)），那么会将边 $(u,v)$ 添加到集合 $A$ 中。

注意，这里的实现会用到并查集这一数据结构。如果采用并查集实现，时间复杂度为 $O(Elg V)$。

Prim 算法：

Prim 算法的过程如下所示：

1. 做一些初始化的操作，包括将结点的 key 值设为 ∞，每个结点的父节点置为 NULL，初始化优先队列 $Q$，设定根结点 $r$ 的 key 值为 0（从这个结点开始执行算法）；
2. 将所有结点塞进优先队列中，实际上 $Q$ 就代表集合 $V-A$。需要注意的是，这其中会涉及到一些优先队列的维护操作，而优先队列是通过堆的方式实现，这里不做过多详述，不了解的只需要知道 $Q$ 支持快速地弹出 key 值最小的结点。
3. 从 $Q$ 中拿出 key 值最小的，之后遍历它的邻接结点，从中挑选出还没有加入到集合 $A$ 中的结点（对应条件 $v in Q$）且 key 值最小，塞进集合 $A$ 中。这个过程同样伴随着更新每个结点的 key 值。

一般我们采用二叉最小堆来实现优先队列，此时 Prim 算法的时间复杂度为 $O(Elg V)$。如果使用斐波那契堆来实现优先队列，则算法复杂度将会改进到 $O(E+Vlg V)$。

以上就是关于最小生成树的学习笔记，包括最小生成树的定义、求解方法以及 Kruskal 算法和 Prim 算法的具体实现。