形式陈述

Kruskal 算法将无向图边按权非降排序，从空森林开始依次扫描；若边两端当前属于不同连通分量，就加入并合并分量。环性质或拟阵贪心定理保证结果为最小生成森林；连通图中恰选 $|V|-1$ 条边得到 MST。排序占 $O(|E|\log |E|)$，并查集操作总计近线性。权重相等时任意一致平局顺序都正确，但输出树可能不同。

直觉

始终考虑全局最便宜的尚可用边，只拒绝会形成环的边。森林约束是图拟阵独立性，因此局部选择可通过交换论证保持最优。

例子与边界

若三角形权重 1、2、10，先选 1 和 2，权 10 因成环被拒绝。不连通图会为每个分量生成 MST，而不是报错。负边会优先选入且不影响正确性。Kruskal 与“每个顶点选最便宜邻边”不同，后者可能成环或不连通。若边权已是小整数，可用计数/基数排序改善排序成本；并查集只维护当前森林分量，不直接证明权重最优。

推论与应用

Kruskal 适合稀疏图、边列表和离线网络构建，也用于单链接聚类和最小瓶颈生成树。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。