本课时有配套视频讲解，购买后即可观看（永久有效）
Kruskal求最小生成树
一、课上练习
编程练习
- 最小生成树(Kruskal)：L49976
二、知识总结
✨ 核心思想
Kruskal 算法是一种经典的贪心算法，用于求解无向连通图的最小生成树（Minimum Spanning Tree, MST）。其核心思想非常简洁：将所有边按权值从小到大排序，然后依次考察每条边，如果这条边连接的两个顶点不在同一个连通分量中，就将其加入生成树。
最小生成树的定义：在一个有 个顶点的无向连通图中，选出 条边，使得所有顶点连通，且这 条边的权值之和最小。
✨ 算法原理
Kruskal 算法的步骤如下：
- 排序：将图中所有边按权值从小到大排序。
- 初始化：每个顶点独自构成一个连通分量（使用并查集维护）。
- 贪心选边：按权值从小到大遍历每条边 ：
- 如果 和 不在同一个连通分量中，则将该边加入生成树，并合并 和 所在的连通分量。
- 如果 和 已经在同一个连通分量中，则跳过该边（加入会形成环）。
- 终止：当已选边数达到 时，最小生成树构建完成。
为什么贪心是正确的？ 这可以用切割定理证明：对于图的任意一个切割，横跨该切割的最小权边一定属于某棵最小生成树。
并查集是 Kruskal 算法的关键数据结构，它支持：
find(x)：查找 所在集合的代表元素（带路径压缩）。unite(x, y)：合并 和 所在的集合（按秩合并）。
✨ 代码实现
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5const int MAXM = 200005;
6
7// 边的结构体
8struct Edge {
9 int u, v, w; // 起点、终点、权值
10 bool operator<(const Edge& other) const {
11 return w < other.w; // 按权值升序排序
12 }
13};
14
15Edge edges[MAXM]; // 存储所有边
16int fa[MAXN]; // 并查集的父节点数组
17int rk[MAXN]; // 并查集的秩（用于按秩合并）
18int n, m; // n个顶点，m条边
19
20// 并查集：查找根节点（带路径压缩）
21int find(int x) {
22 if (fa[x] != x) fa[x] = find(fa[x]);
23 return fa[x];
24}
25
26// 并查集：合并两个集合（按秩合并）
27bool unite(int x, int y) {
28 int fx = find(x), fy = find(y);
29 if (fx == fy) return false; // 已在同一集合
30 if (rk[fx] < rk[fy]) swap(fx, fy);
31 fa[fy] = fx;
32 if (rk[fx] == rk[fy]) rk[fx]++;
33 return true;
34}
35
36int main() {
37 ios::sync_with_stdio(false);
38 cin.tie(nullptr);
39
40 cin >> n >> m;
41
42 // 初始化并查集
43 for (int i = 1; i <= n; i++) {
44 fa[i] = i;
45 rk[i] = 0;
46 }
47
48 // 读入所有边
49 for (int i = 0; i < m; i++) {
50 cin >> edges[i].u >> edges[i].v >> edges[i].w;
51 }
52
53 // 第一步：按权值排序
54 sort(edges, edges + m);
55
56 long long totalWeight = 0; // 最小生成树的总权值
57 int edgeCount = 0; // 已选边数
58
59 // 第二步：贪心选边
60 for (int i = 0; i < m && edgeCount < n - 1; i++) {
61 int u = edges[i].u, v = edges[i].v, w = edges[i].w;
62 if (unite(u, v)) {
63 // u和v不在同一连通分量，加入生成树
64 totalWeight += w;
65 edgeCount++;
66 }
67 }
68
69 // 判断是否成功构建最小生成树
70 if (edgeCount == n - 1) {
71 cout << totalWeight << endl;
72 } else {
73 cout << "impossible" << endl; // 图不连通
74 }
75
76 return 0;
77}✨ 执行示例
以一个简单的图为例，5 个顶点、7 条边：
边列表（排序前）：
(1,2,4) (1,3,2) (2,3,5) (2,4,10) (3,4,3) (3,5,8) (4,5,7)
排序后：
(1,3,2) (3,4,3) (1,2,4) (2,3,5) (4,5,7) (3,5,8) (2,4,10)逐步执行：
| 步骤 | 考察边 | 权值 | 操作 | 已选边数 | 总权值 |
|---|---|---|---|---|---|
| 1 | (1,3) | 2 | 1和3不连通，加入 | 1 | 2 |
| 2 | (3,4) | 3 | 3和4不连通，加入 | 2 | 5 |
| 3 | (1,2) | 4 | 1和2不连通，加入 | 3 | 9 |
| 4 | (2,3) | 5 | 2和3已连通，跳过 | 3 | 9 |
| 5 | (4,5) | 7 | 4和5不连通，加入 | 4 | 16 |
已选 4 = n-1 条边，算法结束。最小生成树权值为 16。
✨ 解题步骤详解
- 建图：读入所有边，存入边数组。
- 排序：对边按权值排序，这是贪心策略的基础。
- 初始化并查集：每个点初始时是独立的集合。
- 遍历选边：从小到大遍历边，用并查集判断是否形成环。
- 判断连通性：如果选了 条边则成功；否则图不连通，无最小生成树。
常见题型变化：
- 最大生成树：将排序改为降序即可。
- 判断最小生成树是否唯一：检查是否存在等权替换边。
- 限制某些边必须选或不选：先处理必选/必不选的边，再正常 Kruskal。
✨ 常见错误
- 忘记初始化并查集：
fa[i]必须初始化为i，否则find函数行为不正确。 - 数组越界：边数组大小应至少为 ，注意双向边是否需要 。
- 权值之和溢出：当边权较大时，总权值可能超过
int范围，应使用long long。 - 未判断图的连通性：如果图不连通，无法构成生成树，需要特判。
- 并查集未使用路径压缩：不使用路径压缩会导致
find退化为 ，整体效率下降。 - 排序方向错误：求最小生成树应升序排序，求最大生成树应降序排序。
✨ 算法评价
| 指标 | 分析 |
|---|---|
| 时间复杂度 | ，排序是瓶颈，并查集操作近乎 |
| 空间复杂度 | ，存储边和并查集 |
| 适用场景 | 稀疏图（ 远小于 ）效果尤佳 |
| 与 Prim 对比 | Kruskal 适合稀疏图，Prim 适合稠密图 |
| 实现难度 | 简单，只需排序 + 并查集 |
Kruskal 算法因其实现简洁、思路清晰，是竞赛中求最小生成树最常用的算法。掌握并查集是理解 Kruskal 的前提。
三、课后练习
编程练习
- 最优布线问题：T1349