Kruskal 算法 | Codeboy's Blog

形式陈述

给定有限无向带权图 $G=(V,E)$ ，Kruskal 算法先把边按权非降排列，令 $F=\varnothing$ 。依次扫描边 $e=uv$ ：若 $u,v$ 位于森林 $(V,F)$ 的不同连通分量，就把 $e$ 加入 $F$ 并合并两分量；否则跳过。并查集用 find(u) != find(v) 检测前一种情形，用 union(u,v) 完成合并。

正确性不变量是 $F$ 为森林，且包含于某棵最小生成森林。考虑下一条被接受的边 $e=uv$ ，令 $S$ 是接受前含 $u$ 的森林分量。割 $(S,V\setminus S)$ 尊重 $F$ 。若有更轻的跨割边 $e'$ ，它更早被扫描；当时 $e'$ 两端也分属不同分量，本应已经合并它们，与当前 $e$ 仍跨分量矛盾。因此 $e$ 是该割的轻边，交换论证保证安全。这给出了算法的贪心证明，而并查集只负责维护可行性。

若原图有 $c$ 个连通分量，最终接受 $|V|-c$ 条边，得到最小生成森林；连通时 $c=1$ ，结果是最小生成树。相同权边可按任意固定顺序扫描，每种顺序都正确，但可能选择不同的最优森林。

设 $n=|V|$ 、 $m=|E|$ 。比较排序耗时 $O(m\log m)$ ；初始化单点集合为 $O(n)$ ，按秩/大小合并并配合路径压缩后，扫描产生的 $O(m)$ 次 find/union 总耗时 $O(m\alpha(n))$ 摊还，额外空间 $O(n)$ （不计边数组）。因此一般总界为 $O(n+m\log m)$ 。若边已按权排序，或小整数键允许经明确字长模型使用线性排序，瓶颈可降为并查集扫描成本。

直觉

Kruskal 把每个顶点先看作一座孤岛，再按造价从低到高开放桥梁。若一座桥连接两座已经互通的岛，它只会制造环而不会扩大可达范围；若连接两个分量，它又是当前能跨过相应分量割的最便宜选择，可以安全保留。

算法的进度由“全局边序”驱动，而非某棵树的前沿。许多小树会同时成长并逐步合并，所以输出不依赖根，也不维护从根到顶点的键。

Kruskal 的边序、并查集分量与边的接受和拒绝 — Kruskal 算法状态示意图

例子与边界

设四个顶点的边权为

ab:1,\quad bc:2,\quad ac:3,\quad cd:4,\quad bd:6.

算法接受 $ab,bc$ ，扫描 $ac$ 时发现两端已经连通，故拒绝这条会闭合三角形的边；随后接受 $cd$ ，总权 $1+2+4=7$ 。直接取排序后的前三条会得到 $ab,bc,ac$ ，既有圈又没有覆盖 $d$ ，说明“取最轻的 $n-1$ 条”缺少避环条件。

负权边只会更早出现，不影响正确性。不连通输入自然停在多个树上，不需要伪造无穷权连接。平行边按独立边 ID 排序：若较轻者已连接两个端点，较重平行边随后会被判为成圈；自环的两个端点从一开始就在同一分量，永远跳过。

相同权边的扫描顺序可能改变树。例如四边形四条边都为 $1$ 时，任取三条不成圈边都最优。若应用要求可复现输出，可把边 ID 加入排序键作确定性平局规则；这只选择某个 MST，不改变权重目标。

推论与应用

Kruskal 很适合边列表与稀疏离线输入，因为主访问模式是一遍排序后顺序扫描。单链接聚类可把当前并查集分量视为簇，在只剩目标簇数时停止；下一条跨簇边的权重就是这一级合并阈值。外存输入的主成本可能是排序 I/O，此时 RAM 的 $O(m\log m)$ 比较数不是完整成本模型。

Prim 算法维护一棵活动树及外部顶点键，Kruskal 维护许多分量与全局边序。Borůvka 算法则每轮为所有分量并行挑选最轻出边并收缩。若图持续插删边，删除一条已选边会要求在线寻找替代跨割边；静态排序和普通并查集都不能支持这种拆分，需另用动态最小生成森林结构。

参考资料

Joseph B. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem,” Proceedings of the American Mathematical Society 7(1), 1956, pp. 48–50。
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，§21.2。
Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，§4.5。

形式陈述 ​

反向链接

形式陈述