一、简述
本节主要介绍一下有关最小生成树的两个算法，即 \(Prim\) 算法和 \(Kruskal\) 算法，适用于无向图。
二、Prim 算法
基本思想
\(Prim\) 算法有一个适用于稠密图的朴素版，时间复杂度是 \(O(n^2)\)，还有一个适用于稀疏图的堆优化版本，时间复杂度为 \(O(mlogn)\)，不过 \(y\) 总说不常用，这里也不介绍了。
朴素版的 \(Prim\) 算法：首先初始化 \(dist\) 数组为正无穷，\(dist\) 数组表示的是每个顶点距离连通块的距离，集合 \(S\) 表示在连通块中的点。
for i = 0 to n: // n次迭代
t 为集合 S 外距离连通块最近的点 // 最初连通块没点，所以按照顺序的话我们会选择到点 1
用 t 更新其余点到连通块也就是集合 S 的距离
将 t 放入集合中
这里给出一个例子，如图
注意：\(Prim\) 算法的思想和 \(Dijkstra\) 算法很想，但是关于 \(dist\) 数组的含义和更新方式是不同的
模板题AcWing858.Prim算法求最小生成树
题目描述
给定一个 \(n\) 个点 \(m\) 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 \(G=(V,E)\)，其中 \(V\) 表示图中点的集合，\(E\) 表示图中边的集合，\(n=|V|\)，\(m=|E|\)。
由 \(V\) 中的全部 \(n\) 个顶点和 \(E\) 中 \(n−1\) 条边构成的无向连通子图被称为 \(G\) 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 \(G\) 的最小生成树。
输入格式
第一行包含两个整数 \(n\) 和 \(m\)。
接下来 \(m\) 行，每行包含三个整数 \(u,v,w\)，表示点 \(u\) 和点 \(v\) 之间存在一条权值为 \(w\) 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
\(1≤n≤500,\)
\(1≤m≤10^5,\)
图中涉及边的边权的绝对值均不超过 \(10000\)。
输入样例
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例
6
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int dist[N];
bool st[N];
int g[N][N];
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 (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == INF) return INF;
if (i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++)
dist[j] = min(dist[j], g[t][j]);
}
return res;
}
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
for(int i = 0; i < m; i ++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(c, g[a][b]);
}
int t = prim();
if(t == INF) puts("impossible");
else printf("%d", t);
return 0;
}
三、Kruskal 算法
基本思想
\(Kruskal\) 算法是一种贪心的思想。我们对于所有的边按照边权进行从小到大排序。然后枚举每一条边 \(a-b\)，如果 \(a\) 和 \(b\) 不连通，将 \(a\) 和 \(b\) 连通。这里的话，使用并查集进行合并操作，并查集可以进行连通块的合并，以及判断二者是否在同一个连通块内。最后判断选择的边数是否比顶点数少一即可。
也就是，我们枚举边，优先选择边权小的边，对于重边不予考虑。
模板题AcWing859.Kruskal算法求最小生成树
题目描述
给定一个 \(n\) 个点 \(m\) 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 \(G=(V,E)\)，其中 \(V\) 表示图中点的集合，\(E\) 表示图中边的集合，\(n=|V|\)，\(m=|E|\)。
由 \(V\) 中的全部 \(n\) 个顶点和 \(E\) 中 \(n−1\) 条边构成的无向连通子图被称为 \(G\) 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 \(G\) 的最小生成树。
输入格式
第一行包含两个整数 \(n\) 和 \(m\)。
接下来 \(m\) 行，每行包含三个整数 \(u,v,w\)，表示点 \(u\) 和点 \(v\) 之间存在一条权值为 \(w\) 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
\(1≤n≤10^5,\)
\(1≤m≤2∗10^5,\)
图中涉及边的边权的绝对值均不超过 \(1000\)。
输入样例
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例
6
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = N * 2;
struct Edge
{
int a, b, w;
bool operator< (const Edge& W) const {
return w < W.w;
}
} edge[M];
int p[N];
int n, m;
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++) p[i] = i;
for (int i = 0; i < m; i ++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edge[i] = {u, v, w};
}
sort(edge, edge + m);
int sum = 0, cnt = 0;
for (int i = 0; i < m; i ++)
{
int a = edge[i].a, b = edge[i].b;
a = find(a), b = find(b);
if (a != b)
{
sum += edge[i].w;
cnt ++;
// cout << b << ' ' << p[b] << endl;
p[a] = p[b];
}
}
if (cnt < n - 1) puts("impossible");
else printf("%d\n", sum);
return 0;
}
四、一个应用
AcWing3728.城市通电
题目描述
平面上遍布着 \(n\) 座城市，编号 \(1∼n\)。
第 \(i\) 座城市的位置坐标为 \((x_i,y_i)\)。
不同城市的位置有可能重合。
现在要通过建立发电站和搭建电线的方式给每座城市都通电。
一个城市如果建有发电站，或者通过电线直接或间接的与建有发电站的城市保持连通，则该城市通电。
在城市 \(i\) 建立发电站的花费为 \(c_i\) 元。
在城市 \(i\) 与城市 \(j\) 之间搭建电线所需的花费为每单位长度 \(k_i+k_j\) 元。
电线只能沿上下左右四个方向延伸，电线之间可以相互交叉，电线都是双向的。
每根电线都是由某个城市沿最短路线搭建到另一个城市。
也就是说，如果在城市 \(i\) 与城市 \(j\) 之间搭建电线，则电线的长度为 \(|x_i−x_j|+|y_i−y_j|\)。
请问，如何合理设计通电方案，可以使得所有城市都成功通电，且花费最少？
输出最少花费和具体方案。
如果方案不唯一，则输出任意一种合理方案均可。
输入格式
第一行包含整数 \(n\)。
接下来 \(n\) 行，其中第 \(i\) 行包含两个整数 \(x_i,y_i\)，用来描述城市 \(i\) 的横纵坐标。
再一行包含 \(n\) 个整数 \(c_1,c_2,…,c_n\)，用来描述每个城市建立发电站的花费。
最后一行包含 \(n\) 个整数 \(k_1,k_2,…,k_n\)。
输出格式
第一行输出所需要的最少花费。
第二行输出一个整数 \(v\)，表示需要建立发电站的数量。
第三行输出 \(v\) 个整数，表示建立发电站的城市编号，注意输出编号要在范围 \([1,n]\) 内。且输出编号不应重复。输出编号顺序随意。
第四行输出一个整数 \(e\)，表示需要搭建的电线数量。
接下来 \(e\) 行，每行输出两个整数 \(a,b\)，表示要在城市 \(a\) 和 \(b\) 之间搭建电线。注意，任意两个城市之间最多只需要搭建一根电线，也就是说，对于每个 \((a,b)\)，不要有多余的 \((a,b)\) 或 \((b,a)\) 输出。\(a\) 和 \(b\) 不能相同，且要在范围 \([1,n]\) 内。输出电线顺序随意。
如果答案不唯一，输出任意合理方案即可。
数据范围
对于前三个测试点，\(1≤n≤3\)。
对于全部测试点，\(1≤n≤2000\)，\(1≤x_i,y_i≤10^6\)，\(1≤c_i,k_i≤10^9\)。
输入样例1
3
2 3
1 1
3 2
3 2 3
3 2 3
输出样例1
8
3
1 2 3
0
输入样例2
3
2 1
1 2
3 3
23 2 23
3 2 3
输出样例2
27
1
2
2
1 2
2 3
解题思路
其实这道题只需要想出一点即可，前面笔者的随笔在写关于 \(Dijkstra\) 算法的题目时，用到了一个虚拟点的技巧(这个技巧也许一直都有，但我是从 \(y\) 总那里学到的，手动滑稽)。也就是我们对于建造发电厂，我们构建虚拟点和各个城市的边，边权为发电厂的建造费用，然后处理正常城市之间修建电线的费用，构建城市之间的边。然后我们就可以应用最小生成树算法了。笔者采用的是 \(Kruskal\) 算法，时间复杂度为 \(O(n^2logn)\)，边数数量级为 \(n^2\)。
C++代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 3010;
typedef long long LL;
typedef pair<int, int> PII;
int n;
struct Point
{
int x, y;
} point[N];
struct Edge
{
int a, b;
LL w;
bool operator< (const Edge &W) const {
return w < W.w;
}
} edge[N * N];
int c[N], k[N];
int p[N];
vector<PII> res;
bool cmp(PII a, PII b)
{
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}
int find(int x)
{
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d", &n);
for (int i = 0; i <= n; i ++)
p[i] = i;
for (int i = 1; i <= n; i ++)
{
int x, y;
scanf("%d%d", &x, &y);
point[i] = {x, y};
}
for (int i = 1; i <= n; i ++)
scanf("%d", &c[i]);
for (int i = 1; i <= n; i ++)
scanf("%d", &k[i]);
int m = 0;
for (int i = 1; i <= n; i ++)
for (int j = i + 1; j <= n; j ++)
{
LL w = (LL) (abs(point[i].x - point[j].x) + abs(point[i].y - point[j].y)) * (k[i] + k[j]);
edge[m ++] = {i, j, w};
}
for (int i = 1; i <= n; i ++)
edge[m ++] = {0, i, (LL) c[i]};
sort(edge, edge + m);
int cnt = 0;
LL sum = 0;
for (int i = 0; i < m; i ++)
{
int a = edge[i].a, b = edge[i].b;
a = find(a), b = find(b);
if (a != b)
{
p[a] = b;
sum += edge[i].w;
cnt ++;
res.push_back({edge[i].a, edge[i].b});
}
}
printf("%lld\n", sum);
sort(res.begin(), res.end());
// 输出电站
int v = 0;
for (int i = 0; i < cnt; i ++)
if (res[i].first == 0)
v ++;
printf("%d\n", v);
for (int i = 0; i < v; i ++)
printf("%d ", res[i].second);
printf("\n");
// 输出线路
int e = cnt - v;
printf("%d\n", e);
if (!e) return 0;
for (int i = v; i < cnt; i ++)
printf("%d %d\n", res[i].first, res[i].second);
return 0;
}