Kruskal 最小生成树

图算法 · 最小生成树（MST）

什么是最小生成树

在一张无向带权连通图里，选出若干条边把所有点连起来、不成环、且总权重最小——这就是最小生成树（MST）。比如要给几个村庄铺电缆，怎么连最省料？

Kruskal 怎么做

把所有边按权重从小到大排序，依次考虑每条边：用并查集判断这条边的两端是否已经连通——没连通就加入生成树（并把两端合并到一组），已连通就跳过（再加它会成环）。选够 V−1 条边就完成。

下面固定一张 6 个点的无向带权图。点「下一步」按权重从小到大逐条考虑：当前边黄色高亮——不成环就加入（变绿）、两端点也连进森林；已连通就成环跳过（灰虚线）。走到底得到 5 条边、总权重最小的生成树。右侧代码随每一步同步高亮。

为什么「每次贪心取不成环的最小边」是对的？由切分定理保证：横跨任意一种分割的最小边，一定属于某棵最小生成树。判环用并查集，几乎是常数时间；整体复杂度由排序主导，约 O(E log E)。判环正是并查集的经典应用。

Kruskal 在哪里用

它把「贪心 + 并查集」用得很漂亮——想复习并查集怎么合并、找根，可回看 数据结构 · 并查集。