Prim 算法
生成树 Spanning Tree
- 对于无向连通图 G 的一个子图，如果它是包含 G 中所有顶点的树，那么这个子图称为 G 的生成树。
- 生成树是无向连通图的包含所有顶点的极小连通子图。
- 在一个无向连通图上，去掉一些边，只保留 V−1 条边，且保持连通
- 图的生成树不唯一
最小生成树 Minimum Spanning Tree
- 生成树各边的权值之和，称为生成树的代价，使代价最小的生成树，称为最小生成树
- 最小生成树在实际生活中有重要的作用：
- 比如，最短修建多少公里的公路可以连通几个城市？
Prim 算法
- 假设 G(V,E) 是连通图， T 是 G 上 MST 中边的集合，将点集 V 分为两部分 {U} 和 {V−U}。任选一点 u0，算法从 U={u0}，T={} 开始，重复执行下述操作：
(1) 在所有 u∈{U}，v∈{V−U} 的边（即横跨集合 {U}/{V−U} 的边）中找最小的边 (u,v) 并入集合 T，同时 v 并入 {U}；
(2) 直到最后 U=V 为止。此时，集合 T 中必有 V−1 条边，则 G(U,T) 为 G 的最小生成树。
朴素算法时间复杂度 V2，可以用优先队列找最小边的过程，复杂度 VlogV。
- 可以用 cost 数组来表示 V−U 集合中，每个点与 U 集合中点的最小距离
- cost 数组初始化成无穷大
- vis 数组表示某个点是否在 U 数组中
模板
int prim() {
for (int i = 0; i <= n; ++i) {
cost[i] = INF;
vis[i] = 0;
}
cost[1] = 0;
int res = 0;
for (int i = 0; i < n; ++i) {
// 寻找cost[index]最小的实点index
int index = 0;
for (int j = 1; j <= n; ++j) {
if (vis[j] == 0 and cost[j] < cost[index]) {
index = j;
}
}
vis[index] = 1; // 把实点变成虚点
res += cost[index]; // 累加权值
// 修改与index相连的所有实点
for (int j = 1; j <= n; ++j) {
if (vis[j] == 0 and cost[j] > adj[index][j]) {
cost[j] = adj[index][j];
}
}
}
return res;
}
Kruskal 算法
用贪心的方式选择边
- 思路：能否尽可能挑选比较小的边加入 MST 中？只要不产生回路即可。
- 首先，所有点都属于各自的树，构成一个森林。从小到大选择不构成回路的边加入到 MST 中，直到所有点成为一颗树。
- 可以使用并查集！
- 步骤：
(1) 所有边按照从小到大的顺序排列
(2) 如果边连续的两个点不属于同一集合，则合并，并把这条边加入 MST
(3) 重复步骤（2），直到所有点在一个集合中
复杂度 ElogE+Eα(V)，其中 ElogE 是排序时间，α(V) 是并查集一次查询的时间复杂度
比较
- Prim：复杂度 O(V2)
- Kruskal: 复杂度 ElogE
- 稀疏图：V 和 E 同数量级，Prim 是 O(V2)，Kruskal 是 O(VlogV) （一般出题是用稀疏图，因为稠密图没什么可优化的）
- 稠密图：E 和 V2 是同数量级，Prim 是 O(V2)，Kruskal 是 O(V2logV2)
模板
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::sort;
const int N = 5005;
const int M = 200005;
// 用于存边
struct Edge{
int u, v, w;
bool operator< (const Edge& edge) const{
return w < edge.w;
}
};
int n, m;
Edge graph[M];
int father[N];
int mst;
int find(int x) {
if (father[x] == x) return x;
return father[x] = find(father[x]);
}
void merge(int x, int y) {
father[find(x)] = find(y);
}
bool kruskal() {
for (int i = 1; i <= n; ++i) father[i] = i;
int cnt = 0; // cnt记录几次合并
sort(graph, graph + m);
for (int i = 0; i < m; ++i) {
Edge e = graph[i];
int u = e.u, v = e.v, w = e.w;
if (find(u) != find(v)) {
merge(u, v), mst += w, cnt++;
if (cnt == n - 1) return true;
}
}
return false;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> graph[i].u >> graph[i].v >> graph[i].w;
}
if (kruskal()) cout << mst << '\n';
else cout << "orz\n";
return 0;
}
最小生成树有两个非常重要的性质，一般的题都离不开这两个性质
-
回路性质：
在原图上任取一个环，环上权值最大的边一定不出现在最小生成树中 -
切割性质：
把节点分为S和T两部分，在所有连接S和T的边中，边权最小的那条一定出现在最小生成树中
用这两个性质可以做很多经典题，比如次小生成树，比如动态加边的最小生成树，比如Codeforces 888G
