不关心"最短距离"，而是关心"用最少、最便宜的边把所有点连通"——按边权从小到大贪心地挑，配合并查集判断会不会成环。
给定一张连通的带权无向图，从中选出一部分边，让所有顶点仍然连通，并且选出的边的权值之和最小——这些边构成的结构就叫最小生成树（Minimum Spanning Tree，简称 MST）。
"生成树"这个名字点出了它的两个特征：树——意味着不能有环，V 个顶点恰好用 V-1 条边连通；生成——意味着它覆盖了原图全部顶点，不能漏掉任何一个点。一张图可能存在多种不同的生成树，而最小生成树是其中边权之和最小的那一种（可能不止一种方案能取到这个最小值，但最小值本身是唯一确定的）。
Kruskal 算法的做法非常直接：把图里所有的边按权值从小到大排序，然后依次考察每一条边——如果这条边的两个端点还没有被连通，就选中这条边（把两个端点合并到同一个连通块）；如果两个端点已经连通了，选中这条边只会形成环（多余、不需要），直接跳过。选够 V-1 条边后，最小生成树就构建完成了。
"判断两个点是不是已经连通"，正是 10.1 节讲过的并查集最擅长的事情——Kruskal 算法可以说是并查集最经典的应用场景之一。
| 步骤 | 做什么 |
|---|---|
| ① 排序 | 把所有边按权值从小到大排序 |
| ② 初始化 | 每个顶点各自成为一个独立的并查集（谁也不连谁） |
| ③ 依次处理 | 按排好的顺序考察每条边 (u, v, w)：如果 Find(u) ≠ Find(v)，选中这条边，Union(u, v)；否则跳过 |
| ④ 结束 | 选中的边数达到 V-1 条时，最小生成树构建完成（也可以处理完所有边后自然结束） |
还是 15.1～15.3 节的示例图（顶点 A B C D，边 A-B=4，A-C=1，B-C=2，B-D=5，C-D=8），先把 5 条边按权值从小到大排序：A-C(1)，B-C(2)，A-B(4)，B-D(5)，C-D(8)，再依次处理：
| 边 | 权值 | Find(u) 与 Find(v) | 结果 | 当前连通块 |
|---|---|---|---|---|
| A-C | 1 | 不同（各自独立） | 选中，Union(A,C) | {A,C} {B} {D} |
| B-C | 2 | 不同（B 独立，C 在 {A,C}） | 选中，Union(B,C) | {A,B,C} {D} |
| A-B | 4 | 相同（A、B 都已在 {A,B,C}） | 跳过——会成环 | {A,B,C} {D} |
| B-D | 5 | 不同（D 独立） | 选中，Union(B,D) | {A,B,C,D} |
| C-D | 8 | 已经选够 V-1=3 条边，提前结束，不用再看 | ||
A-C(1)、B-C(2)、B-D(5)，权值之和 1+2+5=8，这就是最小生成树的总权值。A-B 被跳过的原因很直观：这时候 A 和 B 已经能通过 A-C-B 这条路径连通了，再选一条直接的 A-B 边只会形成一个多余的环，对"连通所有点"这个目标没有任何帮助。| 1 | int parent[MAXN]; // 并查集数组，见 10.1 节 |
| 2 | |
| 3 | int Find(int x) { return parent[x] == x ? x : parent[x] = Find(parent[x]); } |
| 4 | |
| 5 | struct Edge { int u, v, w; }; // 一条边：两个端点 + 边权 |
| 6 | vector<Edge> edges; |
| 7 | |
| 8 | int Kruskal(int n) // n 个顶点，返回最小生成树的总权值（若不连通返回 -1） |
| 9 | { |
| 10 | for (int i = 1; i <= n; i++) parent[i] = i; // 初始化：每个点各自独立 |
| 11 | sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; }); // ★ 按边权从小到大排序 |
| 12 | |
| 13 | int total = 0, cnt = 0; // total：总权值；cnt：已选中的边数 |
| 14 | for (auto& e : edges) |
| 15 | { |
| 16 | if (Find(e.u) == Find(e.v)) continue; // 已经连通，选它只会成环，跳过 |
| 17 | parent[Find(e.u)] = Find(e.v); // 合并两个连通块 |
| 18 | total += e.w; |
| 19 | cnt++; |
| 20 | if (cnt == n - 1) break; // 已经选够 V-1 条边，提前结束 |
| 21 | } |
| 22 | return cnt == n - 1 ? total : -1; // 选出的边不够 V-1 条，说明原图本身就不连通 |
| 23 | } |
Find(e.u) == Find(e.v) 就是"判断会不会成环"，第 17 行 Union 合并连通块——除此之外没有更多的技巧。这也是 Kruskal 常被当作"贪心算法 + 并查集"综合应用的经典入门例题。设顶点数为 V，边数为 E：排序耗时 O(E log E)；之后每条边只需要做一次（近似 O(1) 的）并查集查找和合并操作，总共 O(E)。整体时间复杂度由排序主导，是 O(E log E)。
V²）。如果图很稠密（边数接近 V²），15.5 节的 Prim 算法（从点出发扩展，而不是给边排序）在某些实现下会更有优势——两种算法求出的最小生成树总权值一定相同，选哪个更多是效率和实现习惯上的考量。V-1。第 22 行用 cnt == n-1 判断这种情况，返回 -1 表示"不存在生成树"，而不是把选到的边数直接当成答案返回。Find(e.u)==Find(e.v) 会自动被跳过，不需要额外处理；重边（两点之间有多条边）也不需要提前去重——因为排序后权值小的重边会先被处理并选中，权值大的重边处理时两端点已经连通，自然会被跳过，Kruskal 的判环逻辑天然就能正确处理这两种情况。