Skip to content

最小生成树学习笔记

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

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

#朴素版 Prim 算法

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

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

#思路

Prim 算法运行演示

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

大体步骤如下:

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

#代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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 算法运行演示
  1. 先将所有边按照权重从小到大排序。
  2. 枚举每条边 (a,b,c)(a, b, c),如果 a,ba, b 不连通,将这条边加入集合 SS

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

#代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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,本文其余内容的版权协议见正文下方「版权声明」处。