如何构建一个数据结构的最小生成树？
摘要：最小生成树 前置知识 并查集 图论 概念 条件 最小生成树的满足条件为： 在无向图中选取总权值最少的边让所有点连通。 要求结果是一棵树，边数比点数少 (1)。 当然，最小生成树的结果可能不唯一。 特性 图中任意一条非树边都会和树边构成一
最小生成树
前置知识
并查集
图论
概念
条件
最小生成树的满足条件为：
在无向图中选取总权值最少的边让所有点连通。
要求结果是一棵树，边数比点数少 \(1\)。
当然，最小生成树的结果可能不唯一。
特性
图中任意一条非树边都会和树边构成一个环。
非树边一定是环中最大的边。否则可以替换掉最大的边，得到一个更小生成树。
其他
最小生成树有两种算法：Kruskal 和 Prim。
Kruskal 是在并查集的基础上展开。
Prim 是在最短路的基础上展开。
Kruskal
介绍
我们可以从选边的角度来构造生成树，通过点的连通性来对边的选取进行判断。
我们按权值由小到大选择不成环的边加入树中。（由树的特性可知，成环时该边一定是环中最大的边，不应该选取）。如果选出的边比点数少 \(1\)，说明最小生成树存在，否则不存在。
那么如何快速的判断是否成环？我们可以使用并查集来合并点及判断点的连通性。
步骤
读入所有边并初始化并查集（\(f_i = i\)）。
按权值排序。
合并所有边并计算答案。
输出。
Prim
可以从选点的角度来构造生成树，不断将新的点拉入生成树中。
步骤
读入所有边。
把所有点的距离设为 \(\infty\)，并将任意一点距离设为 \(0\)。
寻找没有进入生成树且距离最小的点进入生成树并累加距离到答案。
更新相邻点距离。
重复 \(3, 4\) 步直到所有点进入生成树。
输出。
证明
假定当前的生成树为 \(A\)，且 \(x\) 是离生成树最近的点。如果 \(x\) 与 \(A\) 的边在最终的生成树中，那么现在可以将 \(x\) 拉入生成树中。如果 \(x\) 与 \(A\) 相连的边不在最终的生成树中，那么 \(x\) 必然要通过另一个当前与 \(A\) 直接相连的点 \(y\)，间接与 \(A\) 相连。那么 \(xA,yA,xy\) 构成环，且 \(xA\) 比 \(yA\) 更短，替换后可以得到更小生成树。
例题 1（洛谷 P3366 【模板】最小生成树）
给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。
原题：https://www.luogu.com.cn/problem/P3366
【Kruskal】
代码是以前写的，可能不好看。
#include <bits/stdc++.h>
using namespace std;
#define qwq ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 200000 + 20, M = 5000 + 50;
struct node {
int x, y, z;
friend bool operator<(const node &a, const node &b) {
return a.z < b.z;
}
};
node edge[N];
int n, m, x, y, z, f[M], l[M], ans = 0;
bool b = 1;
int find(int i) {
if (f[i] == i)
return i;
return f[i] = find(f[i]);
}
void merge(int u, int v) {
u = find(u), v = find(v);
if (l[u] > l[v]) {
swap(l[u], l[v]);
}
f[u] = v;
l[v] += l[u];
}
int main() {
qwq;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
f[i] = i, l[i] = 1;
}
for (int i = 1; i <= m; ++i) {
cin >> edge[i].x >> edge[i].y >> edge[i].z;
}
sort(edge + 1, edge + m + 1);
for (int i = 1; i <= m; ++i) {
if (find(edge[i].x) == find(edge[i].y))
continue;
merge(edge[i].x, edge[i].y);
ans += edge[i].z;
if (l[find(edge[i].x)] == n || l[find(edge[i].y)] == n) {
b = 0;
break;
}
}
if (b)
cout << "orz";
else
cout << ans;
return 0;
}
【Prim】
（摘自洛谷题解）
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define R register int
using namespace std;
int k, n, m, cnt, sum, ai, bi, ci, head[5005], dis[5005], vis[5005];
struct Edge
{
int v, w, next;
} e[400005];
void add(int u, int v, int w)
{
e[++k].v = v;
e[k].w = w;
e[k].next = head[u];
head[u] = k;
}
typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii>> q;
void prim()
{
dis[1] = 0;
q.push(make_pair(0, 1));
while (!q.empty() && cnt < n)
{
int d = q.top().first, u = q.top().second;
q.pop();
if (vis[u])
continue;
cnt++;
sum += d;
vis[u] = 1;
for (R i = head[u]; i != -1; i = e[i].next)
if (e[i].w < dis[e[i].v])
dis[e[i].v] = e[i].w, q.push(make_pair(dis[e[i].v], e[i].v));
}
}
int main()
{
memset(dis, 127, sizeof(dis));
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (R i = 1; i <= m; i++)
{
scanf("%d%d%d", &ai, &bi, &ci);
add(ai, bi, ci);
add(bi, ai, ci);
}
prim();
if (cnt == n)
printf("%d", sum);
else
printf("orz");
}
例题 2（洛谷 P1550 [USACO08OCT] Watering Hole G）
Farmer John 决定将水引入到他的 \(n\) 个农场。他准备通过挖若干井，并在各块田中修筑水道来连通各块田地以供水。在第 \(i\) 号田中挖一口井需要花费 \(W_i\) 元。连接 \(i\) 号田与 \(j\) 号田需要 \(P_{i,j}\)（\(P_{j,i}=P_{i,j}\)）元。
每次输入 \(w_i\) 时，把 \(i\) 和 \(n + 1\) 连接，边权为 \(w_i\)。
然后在输入 \(p\) 数组后，套一个双层循环，如果 \(i \neq j\)，把 \(i\) 和 \(j\) 连接
，边权为 \(p_{i, j}\)。
存完边之后按照边权排序。排序后跑一遍 Kruskal 即可。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long;
#define mtest for (cin >> t; t; -- t)
const int kMaxN = 1e5 + 10, kMaxM = 1010, kInf = (((1 << 30) - 1) << 1) + 1;
const ll kLInf = 9.22e18;
int n, w[kMaxN], f[kMaxN], p[kMaxM][kMaxM], ans = 0;
struct node {
int u, v, w;
} e[kMaxN];
int F(int x) {
return f[x] == x? x : f[x] = F(f[x]);
}
bool cmp(node a, node b) {
return a.w < b.w; // 注意是 <
}
void U(int u, int v, int w) {
int x = F(u), y = F(v);
if (x != y) {
f[f[u]] = f[v];
ans += w;
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i - 1 <= n; ++ i) { // 初始化
f[i] = i;
}
int id = 0;
for (int i = 1; i <= n; ++ i) { // 村边
e[++ id].u = i;
e[id].v = n + 1;
// i & n + 1 连接
cin >> e[id].w;
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
cin >> p[i][j];
}
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
if (i == j) {
continue;
}
e[++ id].u = i;
e[id].v = j;
// i & j 连接
e[id].w = p[i][j];
}
}
sort(e + 1, e + id + 1, cmp); // 按边权排序
for (int i = 1; i <= id; ++ i) { // 跑 Kruskal
U(e[i].u, e[i].v, e[i].w);
}
cout << ans << '\n';
return 0;
}
关联习题
洛谷 P1194 / P1195 / P1396 / P2330 / P2700 / P4047。
CF / AT 上面关于最小生成树的题。