最小生成树学习笔记

在 OI 中常用的最小生成树算法有朴素版 Prim 算法和 Kruskal 算法。

#朴素版 Prim 算法

Prim 算法是一种常见且好写的最小生成树算法。

朴素版 Prim 算法的基本思想是从一个结点开始不断加点，其时间复杂度约为 $O(n^2)$ ，适用于稠密图。

#思路

朴素版的 Prim 算法思想与我在最短路学习笔记一文中提到的朴素版 Dijkstra 算法很相似。

大体步骤如下：

初始化一个 dist 数组，使所有距离均为 $\infty$ 。
设集合 $S$ 表示已经在连通块内的所有点。
进行 $n$ $n$ 次迭代：
1. 找到集合外 $S$ 中的距离最近的点，将其赋值给 $t$ 。
2. 用 $t$ 更新其他点到 集合 $\bold{S}$ 的距离。
3. 将 $t$ 添加到集合 $S$ 中。

#代码

题目： P3366 【模板】最小生成树

C++

#include <bits/stdc++.h>

using namespace std;

int n, m, u, v, w, g[5005][5005], dist[5005];
bool vis[5005];

int prim() {
    memset(dist, 0x3f, sizeof(dist));
    int res = 0;
    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        if (i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
        if (i) res += dist[t];
        for (int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], g[t][j]);
        }
        vis[t] = true;
    }
    return res;
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }
    int ans = prim();
    if (ans == 0x3f3f3f3f) {
        cout << "orz" << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

#Kruskal 算法

时间复杂度约为 $O(m \log m)$ ，适用于稀疏图。

#思路

先将所有边按照权重从小到大排序。
枚举每条边 $(a, b, c)$ ，如果 $a, b$ 不连通，将这条边加入集合 $S$ 。

注：可以使用并查集维护联通块。

#代码

题目： P3366 【模板】最小生成树

C++

#include <bits/stdc++.h>

using namespace std;

int n, m, fa[5005], res, cnt;
struct node {
    int u, v, w;

    bool operator<(const node x) const {
        return w < x.w;
    }
} g[200005];

int find(int x) {
    return fa[x] = fa[x] != x ? find(fa[x]) : fa[x];
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> g[i].u >> g[i].v >> g[i].w;
    }
    sort(g, g + m);
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 0; i < m; i++) {
        g[i].u = find(g[i].u);
        g[i].v = find(g[i].v);
        if (g[i].u != g[i].v) {
            fa[g[i].u] = g[i].v;
            res += g[i].w;
            cnt++;
        }
    }
    if (cnt < n - 1) {
        cout << "orz" << endl;
    } else {
        cout << res << endl;
    }
    return 0;
}

#朴素版 Prim 算法

#思路

#代码

#Kruskal 算法

#思路

#代码

#参考资料