最小生成树

关于最小生成树的经典算法为Prim和Kruskal算法，很多文章都对其算法流程进行了详细的介绍，但对于其算法正确性的证明却常常忽略。笔者最初接触这两个算法的证明来自《算法导论》，但其中关于“安全边”等的繁琐定义和性质让笔者最初感觉不好理解，因此下面主要总结自己的理解。

两个算法都基于贪心的思想，因此理解其正确性证明，对于贪心算法的一般证明思路会有更好的理解。

Prim算法

算法介绍

Prim算法可以理解为让一颗小树不断“长大”的过程，定义已经在部分生成树的结点集合$S$,其他结点集合为$T$,Prim算法不断寻找$S$与$T$的割边中边权最小的那一条加入$S$，让“小树”生长。

正确性证明

证明：Prim算法的贪心性质

设上述流程中加入$S$的边为$(u,v)$, 要证明任意不包含边$(u,v)$的另外一个生成树$M’$，都不会比Prim算法产生的生成树$M$ 更优（边权和更小）。

由生成树的性质，$M’$中必须包含连接结点$u$和结点$v$的一条路径 $u-x_1-x_2-…-v$,且根据Prim算法流程，该路径中所有边的边权均不小于边$(u,v)$的边权。

因此将该路径中的$u-x_1$边替换为$u-v$边，将获得不差于$M’$的生成树$M$.

时间复杂度

Prim算法一般使用最小堆维护结点的集合，每次从堆中取出一个距离已经产生的部分结点集合$S$最近的结点，该操作的代价为$O(lgV)$.

而由于最小生成树包含$O(V)$条边,因此上述操作进行$O(V)$次。

综上，Prim算法的时间复杂度为$O(VlgV)$

Kruskal算法

算法介绍

不同于Prim算法，Kruskal算法以边为单位出发，类似于让一堆最小森林逐步拼接为最小生成树的过程。

Kruskal算法按照边权递减的顺序依次考虑每一条边$u-v$，若加入该边的生成森林不构成环（仍满足森林的定义），则加入，直到所有边都被考虑完了。

正确性证明

证明类似于Prim算法，同样证明贪心性质即可。

对于Kruskal算法每次考虑的边$u-v$,证明任何不包含$u-v$的生成树$M’$都不优于包含该边的生成树$M$.

同理，$M’$不包含$u-v$，就必须包含一条由$u$到$v$的路径$p=u-x_1-x_2-…-x_n-v$. 并且有两种情况，

• 情况1，$p$中存在一条边的边权大于边$u-v$的边权$w$
• 情况2，$p$ 中所有边的边权都小于等于边$u-v$的边权$w$

对于情况1，显然将该边替换为$u-v$，是更优的选择，也是Kruskal算法生成的结果。

对于情况2，此时所有的边都将在边$u-v$之前被考虑，同时Kruskal算法产生的生成森林中将要么已经包含了路径$p$,要么存在比路径$p$更优的连接路径$p$中所有结点的解。

证明：若此时Kruskal算法产生的生成森林中不包含路径$p$,则说明$p$中存在一条边$e$因为加入该边会构成环而不能被加入，说明Kruskal算法已经生成过比路径$p$更优的连接路径$p$中所有结点的解。

因此在情况2下，$u-v$不应该被包含在最终的解中，而根据Kruskal算法该边也不会被包含在最终的解中。

综上，Kruskal算法产生的边都是必须包含在最小生成树的最终解的边，因此Kruskal算法将产生最小生成树。

时间复杂度

Kruskal算法分为两步

• 将边按边权递减排序
• 依次考虑每条边，加入不构成环的边

其中，第一步使用排序算法的复杂度为$O(ElgE)$

第二步采用并查集实现，每次考虑边加入边复杂度为$O(\alpha)$,而总共考虑$O(E)$次，共$O(E\alpha)$ 近似为$O(E)$的复杂度

综上，Kruskal算法总复杂度为$O(ElgE)$