Kruskal 最小生成树
图算法 · 最小生成树（MST）
什么是最小生成树
在一张无向带权连通图里，选出若干条边把所有点连起来、不成环、且总权重最小——这就是最小生成树（MST）。比如要给几个村庄铺电缆，怎么连最省料？
Kruskal 怎么做
把所有边按权重从小到大排序，依次考虑每条边：用并查集判断这条边的两端是否已经连通——没连通就加入生成树（并把两端合并到一组），已连通就跳过（再加它会成环）。选够 V−1 条边就完成。
下面固定一张 6 个点的无向带权图。点「下一步」按权重从小到大逐条考虑：当前边黄色高亮——不成环就加入（变绿）、两端点也连进森林；已连通就成环跳过（灰虚线）。走到底得到 5 条边、总权重最小的生成树。右侧代码随每一步同步高亮。
9 条边按权从小到大排好；MST 空、每个点自成一组
1function kruskal(edges: [number, number, number][], n: number): number {
2 edges.sort((a, b) => a[2] - b[2]);
3 const parent = Array.from({ length: n }, (_, i) => i);
4 const find = (x: number): number => {
5 while (parent[x] !== x) x = parent[x];
6 return x;
7 };
8 let weight = 0;
9 for (const [u, v, w] of edges) {
10 const ru = find(u), rv = find(v);
11 if (ru === rv) continue;
12 parent[ru] = rv;
13 weight += w;
14 }
15 return weight;
16}
边数 E9
当前边-
MST 边数0/5
MST 权重0
成环跳过0
1 / 20
为什么「每次贪心取不成环的最小边」是对的？由切分定理保证：横跨任意一种分割的最小边，一定属于某棵最小生成树。判环用并查集，几乎是常数时间；整体复杂度由排序主导，约 O(E log E)。判环正是并查集的经典应用。
Kruskal 在哪里用
最省布线：电网 / 网络 / 道路连通所有节点、总成本最低。
聚类：建 MST 后切掉最大的几条边，自然分成簇。
近似算法基础（如旅行商问题的近似）。另一种 MST 算法是 Prim（从点集生长）。
聚类：建 MST 后切掉最大的几条边，自然分成簇。
近似算法基础（如旅行商问题的近似）。另一种 MST 算法是 Prim（从点集生长）。
它把「贪心 + 并查集」用得很漂亮——想复习并查集怎么合并、找根，可回看 数据结构 · 并查集。