C++ 最小生成树详解

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

对比项	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;
}

项目	Kruskal	Prim
思路	边贪心	点贪心
数据结构	并查集	优先队列
适合	稀疏图	稠密图
是否依赖起点	否	是
实现难度	⭐⭐	⭐⭐⭐

C++ 最小生成树详解

一、最小生成树（Minimum Spanning Tree）是什么？

1️⃣ 图论基础回顾

2️⃣ 生成树（Spanning Tree）

定义

3️⃣ 最小生成树（MST）

定义

形式化

4️⃣ MST 的性质（非常重要）

性质 1：边数固定

性质 2：权值可能不唯一

性质 3：局部最优 → 全局最优

二、MST 的核心理论基础

1️⃣ 割（Cut）定理（Kruskal / Prim 的理论支撑）

割的定义

割边

割定理（Cut Property）

2️⃣ 环（Cycle）定理

三、Kruskal 算法（边优先）

1️⃣ 算法思想

具体步骤

2️⃣ 为什么不会成环？

3️⃣ 时间复杂度分析

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

5️⃣ 易错点总结（Kruskal）

四、Prim 算法（点优先）

1️⃣ 算法思想

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

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

4️⃣ 时间复杂度

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

6️⃣ Prim 常见坑

五、Kruskal vs Prim 对比总结

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

1️⃣ 判断 MST 是否唯一

2️⃣ 次小生成树

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

4️⃣ 动态 MST（了解）

七、典型例题（洛谷）

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具