C++ 最小生成树详解

在一个环中，权值最大的边 不可能出现在 MST 中

这解释了：

• Kruskal 为什么'遇到成环就跳过'
• Prim 为什么只扩展最小边

三、Kruskal 算法（边优先）

1️⃣ 算法思想

一句话总结：

按边权从小到大排序，能加就加，不成环就要

具体步骤

1. 将所有边按权值从小到大排序
2. 初始化并查集（每个点自成一个集合）
3. 枚举每条边 ((u,v))
   • 若 find(u) != find(v) → 加入 MST → 合并集合
4. 当选满 (n-1) 条边，结束

2️⃣ 为什么不会成环？

• 并查集维护的是'连通块'
• 若两点已经在同一集合
  • 说明路径已存在
  • 再连 → 必然成环

3️⃣ 时间复杂度分析

• 排序：(O(m \log m))
• 并查集：近似 (O(1))
• 总体： \[ O(m \log m) \]

适合：

• 稀疏图
• (m) 较小

4️⃣ C++ 实现（竞赛标准写法）

#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;
}

5️⃣ 易错点总结（Kruskal）

❌ 忘记判断图是否连通 ❌ 并查集未路径压缩 ❌ 边数达到 n-1 还继续枚举 ❌ 权值用 int 溢出

四、Prim 算法（点优先）

1️⃣ 算法思想

从一个点开始，每次选一条连接'已选点集'和'未选点集'的最小边

与 Dijkstra 非常像，但本质不同。

2️⃣ 算法步骤（堆优化版）

1. 随机选一个起点
2. 将起点加入 MST
3. 用优先队列维护：
   • 所有'已访问点 → 未访问点'的边
4. 每次取最小边
5. 若终点未访问 → 加入 MST
6. 重复直到选满 (n-1) 条边

3️⃣ 与 Dijkstra 的区别（常考）

4️⃣ 时间复杂度

• 堆优化： \[ O(m \log n) \]

适合：

• 稠密图
• 邻接表结构

5️⃣ C++ 实现（堆优化）

#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;
}

6️⃣ Prim 常见坑

⚠️ 图必须连通 ⚠️ 初始点权值为 0 ⚠️ 不要重复加边权 ⚠️ vis 判断必须在弹出后

五、Kruskal vs Prim 对比总结

六、MST 进阶与拓展（OI 必看）

1️⃣ 判断 MST 是否唯一

方法：

• 若存在 相同权值边
• 且在同一割中可以替换 → 不唯一

竞赛中常结合 次小生成树

2️⃣ 次小生成树

权值严格大于 MST，且最小

做法：

• 枚举非 MST 边
• 替换路径中最大边

需要：

• LCA + 最大边维护

3️⃣ Kruskal 重构树（提高级）

用于：

• MST 上的路径最大/最小查询
• 多用于 离线问题

4️⃣ 动态 MST（了解）

• 边动态增删
• 通常使用：
  • LCT（Link-Cut Tree）

七、典型例题（洛谷）

• P3366 【模板】最小生成树
• P2872 工程规划
• P4180 严格次小生成树