一、最小生成树(Minimum Spanning Tree)是什么?
1️⃣ 图论基础回顾
我们先明确研究对象:
- 无向图
- 连通
- 带权图
设图 (G = (V, E))
- (V):点集,(|V| = n)
- (E):边集,(|E| = m)
- 每条边有权值 (w)
C++ 中最小生成树(MST)的概念、性质及两种核心算法:Kruskal 与 Prim。涵盖图论基础、割定理与环定理、算法实现步骤、时间复杂度分析及代码示例。对比了 Kruskal 与 Prim 的适用场景,并介绍了次小生成树等进阶内容,适合算法竞赛学习者参考。
我们先明确研究对象:
设图 (G = (V, E))
一棵 生成树 满足:
👉 一个连通图可能有 很多棵生成树
在 所有生成树 中,边权之和最小 的那一棵,称为:
最小生成树(Minimum Spanning Tree)
令生成树 (T\subseteq E),使得:
\[ \sum_{e\in T} w(e) \]
取得最小值。
这是 MST 算法正确性的核心依据(贪心基础)。
将点集 (V) 划分为两个非空集合:
\[ S \quad|\quad V-S \]
称为一个 割(Cut)
对于任意一个割,权值最小的割边,一定属于某棵 MST
⚠️ 重点:
在一个环中,权值最大的边 不可能出现在 MST 中
这解释了:
一句话总结:
按边权从小到大排序,能加就加,不成环就要
find(u) != find(v)
→ 加入 MST
→ 合并集合适合:
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int u, v;
long long w;
};
vector<Edge> edges;
int fa[200005];
int find(int x){
if(fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int main(){
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;
long long 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;});
long long 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;
return 0;
}
❌ 忘记判断图是否连通 ❌ 并查集未路径压缩 ❌ 边数达到 n-1 还继续枚举 ❌ 权值用 int 溢出
从一个点开始,每次选一条连接'已选点集'和'未选点集'的最小边
与 Dijkstra 非常像,但本质不同。
| 对比项 | Prim | Dijkstra |
|---|---|---|
| 目标 | 最小生成树 | 最短路径 |
| dist 含义 | 到 MST 的最小边 | 到源点最短距离 |
| 累加方式 | 不累加路径 | 路径累加 |
适合:
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int to;
long long w;
};
vector<Edge> g[200005];
bool vis[200005];
int main(){
int n, m; cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v;
long long w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
long long 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;
return 0;
}
⚠️ 图必须连通 ⚠️ 初始点权值为 0 ⚠️ 不要重复加边权 ⚠️ vis 判断必须在弹出后
| 项目 | Kruskal | Prim |
|---|---|---|
| 思路 | 边贪心 | 点贪心 |
| 数据结构 | 并查集 | 优先队列 |
| 适合 | 稀疏图 | 稠密图 |
| 是否依赖起点 | 否 | 是 |
| 实现难度 | ⭐⭐ | ⭐⭐⭐ |
方法:
竞赛中常结合 次小生成树
权值严格大于 MST,且最小
做法:
需要:
用于:

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML转Markdown 互为补充。 在线工具,Markdown转HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML转Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online