发现了一个梳理的比较系统，该有的都有，而且描述清楚的博主hhhh。以下内容中，有些描述来自他的博客——
Prim原理O(n^2)
Kruskal原理O(eloge)
另外，刷王道大题的时候看到了另一种求MST的方法——破圈法。
最小生成树
问题：如何用最小的“代价”用N-1条边连接N个点
答：最小 总边权重 生成树
- 前提：无向连通图
- Minimum Spanning Tree, MST
- 最小生成树存在当且仅当图是连通的，可能不唯一。
- 树：无环，连通。
- 连通图的生成树：包含图的所有顶点
Prim算法
适合稠密图，O(V^2)，V为顶点数。
思想
贪心，每次只添加从外部连接到该子树的所有边中的最短边即可。
- 从某个顶点开始（看成只有一个结点的子生成树）
- 在当前生成树到外部的相邻边中，选一条权重最小的边，将这条边和边的另一个顶点并入子生成树中（生成树就长大了一点）
继续，直到所有的顶点都被并入了生成树。
类比Dijkstra来看，就是选距离MST最近的外部顶点加入MST。
实现
- 用inMST布尔数组来记录某顶点是否已经在当前的生成树中
- dist数组记录顶点到MST的距离
int new_d = graph[curr][j]; //注意
dist[j] = min(dist[j], new_d);
#include <cstdio>
#include <algorithm>
#define MAXN 1001
#define INF 0x3fffffff
using namespace std;
int graph[MAXN][MAXN], n_vertex, m_edge, total_weight = 0;
void Prim(int start) {
int dist[MAXN];
fill(dist, dist + MAXN, INF);
bool inMST[MAXN] = {false};
dist[start] = 0;
int pre = -1;
for (int i = 0; i < n_vertex; ++i) { // loop: n
int min_dist = INF, curr = -1;
for (int j = 0; j < n_vertex; ++j) {
if (!inMST[j] && dist[j] < min_dist) {
min_dist = dist[j];
curr = j;
}
}
if (curr == -1) {
printf("NOT CONNECTED\n");
return;
}
inMST[curr] = true;
total_weight += dist[curr];
for (int j = 0; j < n_vertex; ++j) {
if (!inMST[j] && graph[curr][j] != INF) {
int new_d = graph[curr][j]; //注意
dist[j] = min(dist[j], new_d);
}
}
}
}
// premise: 连通图
int main() {
scanf("%d%d", &n_vertex, &m_edge);
int v1, v2, weight;
fill(graph[0], graph[0] + MAXN * MAXN, INF);
for (int i = 0; i < m_edge; ++i) {
scanf("%d%d%d", &v1, &v2, &weight);
graph[v1][v2] = graph[v2][v1] = weight;
}
// 不妨从第一个结点开始（结点下标从0开始）
Prim(0);
printf("MST total weight: %d\n", total_weight);
return 0;
}
Kruskal算法
适用于稀疏图，复杂度 O（E log E），E为边数。
思想
为使生成树上边的权值之和达到最小，应使生成树中每一条边的权值尽可能地小。
- 每一轮从边集中选一条权值最小的边，将其两个顶点并入到生成树中，直到全部顶点都在生成树中。
- 对所选边的要求：并入不会形成环，若成环，选下一个权值最小边。
- 判断并入是否成环：并查集(不相交集合)
⚠️用一个visited布尔数组来确保仅加入一次是不够的，例如：已经加入了0---1，2---4，再加入2---1，连接两个分支，就会误判= =，使用并查集是必要的！！！
实现
边集 set<pair<int, pair<int, int >>> edges 自带排序。
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
#define MAXN 1001
using namespace std;
set<pair<int, pair<int, int >>> edges; //set自带排序 嘻嘻
vector<pair<int, pair<int, int >>> MST;
int uf[MAXN];
int _find(int me) {
return uf[me] < 0 ? me : uf[me] = _find(uf[me]);
}
void _union(int a, int b) {
a = _find(a);
b = _find(b);
if (a != b) {
int mm = min(a, b), MM = max(a, b);
uf[mm] += uf[MM];
uf[MM] = mm;
}
}
// premise: 连通图
int main() {
int n_vertex, m_edge;
scanf("%d%d", &n_vertex, &m_edge);
int v1, v2, weight;
fill(uf, uf + MAXN, -1);
for (int i = 0; i < m_edge; ++i) {
scanf("%d%d%d", &v1, &v2, &weight);
edges.insert(make_pair(weight, make_pair(v1, v2)));
}
// select n_vertex-1 edge to build an MST
int total_weight = 0;
pair<int, pair<int, int>> temp_e;
int va, vb;
while (!edges.empty()) {
temp_e = *edges.begin();
edges.erase(edges.begin());
va = temp_e.second.first, vb = temp_e.second.second;
if (_find(va) != _find(vb)) {
_union(va, vb);
MST.emplace_back(temp_e);
total_weight += temp_e.first;
if (MST.size() == n_vertex - 1) break;
}
}
puts("******** MST ********");
for (auto item: MST) {
printf("V%d ---- %d ---- V%d\n", item.second.first, item.first, item.second.second);
}
printf("MST total weight: %d\n", total_weight);
return 0;
}
破圈法（前提：无向连通图）
- 策略
找到图中的一个环，删去环上权重最大的边。重复这个过程，直到图中不存在环了。 - 正确性证明
破圈法最终留下的一定是一棵生成树，因为连通且无环。
关键是 证明它是总边权最小的生成树。
将破圈法得到的树记作T。假设T不是最小生成树，那一定存在最小生成树T0。
取T0和T的并集G'，因为两棵树“枝杈”不同，但点集都是V，所以G'中一定有环。
按破圈法处理G'，删掉环上的最大边，那么得到的树（就是T啦）一定是从G'能得到的最小生成树，与假设矛盾，得证。
网友评论