Kruskal 算法

设 T 是结果边集，初始时其值为空

• 从原图的剩余边中选择代价最小的边

• 判断其与 T 中的边是否形成环

  • 如果是，则丢弃该边
  • 否则，将其加入到 T 中

• 重复执行上面的过程，直到原图中没有剩余的边

证明

首先，证明 Kruskal 算法生成的图是生成树

如果一个图不是生成树，那么分为两种情况：

• 图中有环

  因为每次加入边时，都不会形成环，所以 Kruskal 算法生成的图一定没有环

• 图不连通

  原图中的边会被逐个地加入到 T 中，除非其与 T 中已有的边形成环，因为去掉环上的任意一条边，不会破坏连通性，并且原图是连通图，所以 Kruskal 算法生成的图一定是连通图

综上所述，Kruskal 算法生成的图是生成树

然后，证明 Kruskal 算法生成的生成树是最小生成树

设：

• Kruskal 算法生成的生成树是 T
• U 是原图的一棵最小生成树
• 原图的顶点数为 n，T 和 U 中不同的边的条数为 k，其它 n - 1 - k 条边相同，这 n - 1 - k 条边构成边集 E
• 在 T 中而不在 U 中的边，按代价从小到大依次为 a1、a2、...、ak
• 在 U 中而不在 T 中的边，按代价从小到大依次为 x1、x2、...、xk

现在通过把 U 转换为 T，即将 T 中的边加入到 U，来证明 U 和 T 具有相同的代价。

首先将 a1 加入到 U 中，因为 U 是生成树，所以加入 a1 后，必然形成一个环，且这个环必然包含 x1、x2、...、xk 中的边。（否则，a1 与 E 形成环，而 E 也在 T 中，这与 T 中无环相矛盾）

删除这个环中属于 x1、x2、...、xk，且代价最大的边 xi，构成一个新的生成树 V。

假设 a1 大于 xi，按照 Kruskal 算法，xi 应该在 a1 之前被考虑，而 a1 在 a2、...、ak 之前被考虑，所以在考虑 xi 之前，T 中的边只能是 E 中的边。而 xi 既然没有被加入到 T，说明其必然与 E 中的边形成环。xi 和 E 都在 U 中，这与 U 是生成树相矛盾，所以 a1 不大于 xi。

假设 a1 小于 xi，那么 V 的代价小于 U 的代价，这于 U 是最小生成树相矛盾，所以 a1 不小于 xi。

综上所述，a1 等于 xi，所以 V 的代价等于 T 的代价。

依此类推，将 a2、...、ak 逐个地加入到 U，最终得到的树 T 与 U 具有相同的代价

参考文档

• http://blog.sina.com.cn/s/blog_70ec9a6f01012c0y.html