Road Map

最小生成树

边权和最小的生成树

Minimum Spanning Tree, MST

Kruskal 算法

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。

算法思路：

• 将所有边按权重从小到大排序 O(mlogm)
• 枚举每条边u <--> v,权重 w
  • if a,b 不连通 - 将这条边加入集合中 前置知识：贪心、并查集

应用场景

稀疏图的 最小生成树

代码实现

• AcWing 859. Kruskal 算法求最小生成树

/*
res 最小生成树中的权重之和
cnt 当前加了多少条边
1.将所有边按权重排序O(mlogm)
2.枚举每条边（并查集应用）
    if a,b 不连通
        加入集合
3.需重载<
bool operator < (const Edge &C) const {
    return w < C.w;
}
*/
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10, M = 2e5+10, INF = 0x3f3f3f3f;
int n, m; // n个点，m条边
int f[N]; // 并查集
struct Edge{
    int u, v, w;
    bool operator < (const Edge&e) const{
        return w < e.w; // 按权重从小到大排序
    }
}edges[M];

int find(int x){
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}
int kruskal(){
    sort(edges, edges+m);
    for (int i =0; i<= n; i++)f[i] = i; // 初始化并查集

    int res = 0, cnt = 0; // res:最小生成树权重之和；cnt:增加了多少条边
    for (int i = 0; i <m; i++){
        auto e = edges[i];
        int p = find(e.u), q = find(e.v);
        if (p != q){
            f[q] = p;
            res += e.w;
            cnt++;
        }
    }
    if (cnt < n-1) return INF;
    return res;
}

int main(){
    cin >> n >> m;
    int u, v, w;
    for(int i = 0; i<m; i++){
        cin >> u >> v >> w;
        edges[i] = {u, v, w};
    }

    int ans = kruskal();
    if (ans > INF/2) puts("impossible");
    else cout << ans << endl;

    return 0;
}

Prim 算法

朴素版 Prim 算法

代码实现

• Acwing 858. Prim 算法求最小生成树

/*
S:当前已经在联通块中的所有点的集合
1. dist[i] = inf
2. for n 次
    t<-S外离S最近的点
    利用t更新S外点到S的距离
    st[t] = true
n次迭代之后所有点都已加入到S中
联系：Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离
*/
#include<bits/stdc++.h>
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m; // n个点，m条边
int g[N][N];// 邻接矩阵
int dist[N]; // 存储其他点到S的距离
bool st[N]; // 是否已得到最短距离
int prim(){
    memset(dist, INF, sizeof dist);
    int res = 0;// 如果图不连通，返回INF，否则返回res

    for (int i = 0; i<n; i++){ // n次迭代，将n个点加入集合
        int t = -1; // 找到距离集合最近的点
        for (int j =1; j <= n; j++){
            if (!st[j] && (t == -1 || dist[t] > dist[j])){
                t = j;
            }
        }
        // 找到了距离集合S 最近的点t
        if (i && dist[t] == INF) return INF; // 不连通

        if (i) res += dist[t];
        st[t] = true;
        // 更新到集合S的最短距离
        for (int j = 1; j <=n; j++) dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}
int main(){
    cin >> n >> m;
    for (int i = 1; i <=n ;i++){
        for (int j = 1; j <=n; j++){
            if (i == j) g[i][j] = 0;
            else g[i][j] = INF;
        }
    }
    int u, v, w;
    while (m--){
        cin >> u >> v>> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }
    int t = prim();
    if (t == INF) puts("impossible");
    else cout << t << endl;
    return 0;
}