最小生成树 MST

· · 算法·理论

2025S T2生成树题，没学过写炸了望周知。

定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

Kruskal

该算法的基本思想是从小到大加入边，是贪心算法。即维护一个森林，查询两个结点是否在同一棵树中，连接两棵树。

做法：

  1. 将图中的所有边按权值从小到大排序

  2. 遍历每一条边，检查两边的点是否在同一集合（或者说在同一棵树上）。如果在，则跳过；如果不在，就合并（此处充分的利用 并查集 的查找和合并两大功能）

复杂度为 O(m\log m)

P1195 口袋的天空

#include<bits/stdc++.h>
using namespace std;

const int MAX = 1e5+5;
int fa[MAX], n, m, k;
struct Edge{int u, v, w;} g[MAX];

int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void merge(int a, int b) {fa[find(a)] = fa[find(b)];}
void init(int n) {for(int i=0; i<=n; i++) fa[i] = i;}
bool cmp(Edge a, Edge b) {return a.w < b.w;}

void kruskal()
{
    int total = 0; // 已选了的边数
    int ans = 0; // 总的代价
    for(int i=1; i<=m; i++)
        if(find(g[i].u) != find(g[i].v))
        {
            merge(g[i].u, g[i].v);
            total ++;
            ans += g[i].w;
            if(total == n - k) {cout << ans; return;}
        }
    cout << "No Answer";
}

int main()
{
    cin >> n >> m >> k;
    if(n == k) {cout << 0; exit(0);}
    init(n);
    for(int i=1; i<=m; i++)
        cin >> g[i].u >> g[i].v >> g[i].w;
    sort(g+1, g+m+1, cmp);
    kruskal();
    return 0;
}

Prim

该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。具体地，每次要选择距离最小的一个结点，以及用新的边更新其他结点的距离。和 dijkstra 算法很相似。

复杂度：暴力 O(n^2+m)；堆优化 O((n+m) \log n)

即便是堆优化，复杂度也不优于 Kruskal，常数也比 Kruskal 大。所以，一般情况下都使用 Kruskal 算法，在稠密图尤其是完全图上，暴力 Prim 的复杂度比 Kruskal 优，但也不一定实际跑得更快。不過有且僅有的優點是和 dijkstra 很相似，可以很快的從最短路改為最小生成樹（怒怒）。

而且需要注意， Prim 算法生成的是单个连通分量的最小生成树。多个连通分量的最小生成树如上题复杂度将会提高到 O(n^3)。

#include<bits/stdc++.h>
using namespace std;

const int MAX = 2e5+5;
const int INF = 0x3f3f3f3f;

struct Edge{
    int v, w;
    bool operator>(const Edge& a) const {return w > a.w;}
};
priority_queue<Edge, vector<Edge>, greater<Edge>> q;
vector<Edge> e[MAX];
int n, m, k, vis[MAX], dis[MAX], cnt=0, ans=0;

void prim()
{
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0; q.push({1, 0});

    while(!q.empty())
    {
        if(cnt >= n) break;
        int u = q.top().v, w = q.top().w;
        q.pop();

        if(vis[u]) continue;
        vis[u] = 1;
        ++cnt, ans += w;
        for(auto t : e[u])
            if (t.w < dis[t.v]) 
                dis[t.v] = t.w, q.push({t.v, t.w});
    }
}

signed main()
{
    cin >> n;

    for(int i=1; i<=n; i++)
    {
        int u, v;
        cin >> u >> v >> w;
        e[u].push_back((Edge){v, w});
        e[v].push_back((Edge){u, w});
    }
    prim();
    if(cnt == n) cout << ans;
    else cout << "No MST";

    return 0;
}

後記

對於 MST 問題，Kruskal 算法就已足夠處理所有最小生成樹問題了。

写完文章看了之前的递交记录发现其实是学过的，不过是两年前学的！ ！ ！呜呜已经全忘光了呢...