c++最小生成树详讲
一、最小生成树（Minimum Spanning Tree）是什么？
1️⃣ 图论基础回顾
我们先明确研究对象：
- 无向图
- 连通
- 带权图
设图 (G = (V, E))
- (V)：点集，(|V| = n)
- (E)：边集，(|E| = m)
- 每条边有权值 (w)
2️⃣ 生成树（Spanning Tree）
定义
一棵 生成树 满足：
- 包含图中 所有顶点
- 是一棵 树
- 连通
- 无环
- 边数一定是：
[
|E| = n - 1
]
👉 一个连通图可能有 很多棵生成树
3️⃣ 最小生成树（MST）
定义
在 所有生成树 中，边权之和最小 的那一棵，称为：
最小生成树（Minimum Spanning Tree）
形式化
令生成树 (T\subseteq E)，使得：
[
\sum_{e\in T} w(e)
]
取得最小值。
4️⃣ MST 的性质（非常重要）
性质 1：边数固定
- 任意 MST 的边数 = (n-1)
性质 2：权值可能不唯一
- MST 不一定唯一
- 但 最小权值和一定唯一
性质 3：局部最优 → 全局最优
这是 MST 算法正确性的核心依据（贪心基础）。
二、MST 的核心理论基础
1️⃣ 割（Cut）定理（Kruskal / Prim 的理论支撑）
割的定义
将点集 (V) 划分为两个非空集合：
[
S \quad|\quad V-S
]
称为一个 割（Cut）
割边
- 连接 (S) 和 (V-S) 的边
割定理（Cut Property）
对于任意一个割，权值最小的割边，一定属于某棵 MST
⚠️ 重点：
- 不一定属于所有 MST
- 但一定属于 至少一棵 MST
2️⃣ 环（Cycle）定理
在一个环中，权值最大的边 不可能出现在 MST 中
这解释了：
- Kruskal 为什么“遇到成环就跳过”
- Prim 为什么只扩展最小边
三、Kruskal 算法（边优先）
1️⃣ 算法思想
一句话总结：
按边权从小到大排序，能加就加，不成环就要
具体步骤
- 将所有边按权值从小到大排序
- 初始化并查集（每个点自成一个集合）
- 枚举每条边 ((u,v))
- 若
find(u) != find(v)
→ 加入 MST
→ 合并集合
- 若
- 当选满 (n-1) 条边，结束
2️⃣ 为什么不会成环？
- 并查集维护的是“连通块”
- 若两点已经在同一集合
- 说明路径已存在
- 再连 → 必然成环
3️⃣ 时间复杂度分析
- 排序：(O(m \log m))
- 并查集：近似 (O(1))
- 总体：
[
O(m \log m)
]
适合：
- 稀疏图
- (m) 较小
4️⃣ C++ 实现（竞赛标准写法）
#include<bits/stdc++.h>usingnamespace std;structEdge{int u, v;longlong w;}; vector<Edge> edges;int fa[200005];intfind(int x){if(fa[x]== x)return x;return fa[x]=find(fa[x]);}intmain(){int n, m; cin >> n >> m;for(int i =1; i <= n; i++) fa[i]= i;for(int i =0; i < m; i++){int u, v;longlong w; cin >> u >> v >> w; edges.push_back({u, v, w});}sort(edges.begin(), edges.end(),[](Edge a, Edge b){return a.w < b.w;});longlong ans =0;int cnt =0;for(auto e : edges){int fu =find(e.u);int fv =find(e.v);if(fu != fv){ fa[fu]= fv; ans += e.w; cnt++;if(cnt == n -1)break;}} cout << ans << endl;return0;}5️⃣ 易错点总结（Kruskal）
❌ 忘记判断图是否连通
❌ 并查集未路径压缩
❌ 边数达到 n-1 还继续枚举
❌ 权值用 int 溢出
四、Prim 算法（点优先）
1️⃣ 算法思想
从一个点开始，每次选一条连接“已选点集”和“未选点集”的最小边
与 Dijkstra 非常像，但本质不同。
2️⃣ 算法步骤（堆优化版）
- 随机选一个起点
- 将起点加入 MST
- 用优先队列维护：
- 所有“已访问点 → 未访问点”的边
- 每次取最小边
- 若终点未访问 → 加入 MST
- 重复直到选满 (n-1) 条边
3️⃣ 与 Dijkstra 的区别（常考）
| 对比项 | Prim | Dijkstra |
|---|---|---|
| 目标 | 最小生成树 | 最短路径 |
| dist 含义 | 到 MST 的最小边 | 到源点最短距离 |
| 累加方式 | 不累加路径 | 路径累加 |
4️⃣ 时间复杂度
- 堆优化：
[
O(m \log n)
]
适合：
- 稠密图
- 邻接表结构
5️⃣ C++ 实现（堆优化）
#include<bits/stdc++.h>usingnamespace std;structEdge{int to;longlong w;}; vector<Edge> g[200005];bool vis[200005];intmain(){int n, m; cin >> n >> m;for(int i =0; i < m; i++){int u, v;longlong w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w});} priority_queue<pair<longlong,int>, vector<pair<longlong,int>>, greater<pair<longlong,int>>> pq;longlong ans =0; pq.push({0,1});// 从 1 号点开始while(!pq.empty()){auto[w, u]= pq.top(); pq.pop();if(vis[u])continue; vis[u]=true; ans += w;for(auto e : g[u]){if(!vis[e.to]){ pq.push({e.w, e.to});}}} cout << ans << endl;return0;}6️⃣ Prim 常见坑
⚠️ 图必须连通
⚠️ 初始点权值为 0
⚠️ 不要重复加边权
⚠️ vis 判断必须在弹出后
五、Kruskal vs Prim 对比总结
| 项目 | Kruskal | Prim |
|---|---|---|
| 思路 | 边贪心 | 点贪心 |
| 数据结构 | 并查集 | 优先队列 |
| 适合 | 稀疏图 | 稠密图 |
| 是否依赖起点 | 否 | 是 |
| 实现难度 | ⭐⭐ | ⭐⭐⭐ |
六、MST 进阶与拓展（OI 必看）
1️⃣ 判断 MST 是否唯一
方法：
- 若存在 相同权值边
- 且在同一割中可以替换
→ 不唯一
竞赛中常结合 次小生成树
2️⃣ 次小生成树
权值严格大于 MST，且最小
做法：
- 枚举非 MST 边
- 替换路径中最大边
需要：
- LCA + 最大边维护
3️⃣ Kruskal 重构树（提高级）
用于：
- MST 上的路径最大/最小查询
- 多用于 离线问题
4️⃣ 动态 MST（了解）
- 边动态增删
- 通常使用：
- LCT（Link-Cut Tree）
七、典型例题（洛谷）
- P3366 【模板】最小生成树
- P2872 工程规划
- P4180 严格次小生成树
