最小生成树学习笔记

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

朴素版 Prim 算法

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

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

思路

Prim 算法运行演示Prim 算法运行演示

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

大体步骤如下:

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

代码

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

#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(mlogm)O(m \log m) ,适用于稀疏图。

思路

Krustal 算法运行演示Krustal 算法运行演示
  1. 先将所有边按照权重从小到大排序。
  2. 枚举每条边 (a,b,c)(a, b, c),如果 a,ba, b 不连通,将这条边加入集合 SS

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

代码

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

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

参考资料

  1. 最小生成树 - OI Wiki
  2. 最小生成树 - 维基百科
  3. Prim 算法 - 维基百科
  4. Kruskal 算法 - 维基百科

本文中 Prim 算法的演示图片原稿来自维基共享资源,原作者为 Alexander Drichel ,经本人整合后以 CC BY-SA 3.0 协议发布,初版可见 caf2ba8@OI-wiki/OI-wiki,本文其余内容的版权协议见正文下方「版权声明」处。

最小生成树学习笔记
本文作者
宝硕
发布于
2021-08-27
许可协议
喜欢这篇文章?为什么不考虑打赏一下作者呢?
爱发电
文章目录
  1. 朴素版 Prim 算法
    1. 思路
    2. 代码
  2. Kruskal 算法
    1. 思路
    2. 代码
  3. 参考资料