给定图$G=(V,E)$，其最小生成树为边权值和最小的树，并且联通了图中所有的点，设$MST$为$G$的最小生成树，那么有$MST.edgeSize=V.vertexSize-1$，意思是MST的边数一定为图中顶点数目减去1.
最小生成树常用的两种算法分别是Prim和Kruskal，这两种算法都有对应的堆优化方法，我们先从暴力的解法做起。
Prim算法
思路是给定一个起点顶点s，在s的领域寻找边最短的路径，找到后并加入到最小生成树中。之后便更新最短路径。以此往复就可以生成一个MST了。
暴力解法：
不带路径输出版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void prim(int s) {
int sum = 0;
visit[s] = true;
lowCost = adjmat[s];
for(int i = 1; i < n; i++) {
int minW = INT_MAX, now = -1;
for(int j = 0; j < n; j++) {
if(!visit[j] && lowCost[j] <= minW) {
minW = lowCost[j];
now = j;
}
}
if(now != -1) {
sum += minW;
visit[now] = true;
}
for(int j = 0; j < n; j++) {
if(!visit[j]) lowCost[j] = min(lowCost[j], adjmat[now][j]);
}
}
}
|
带路径输出版
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
| void prim(int s) {
int sum = 0;
for(int i = 0; i < n; i++) parent[i] = i;
visit[s] = true;
lowCost = adjmat[s];
for(int i = 1; i < n; i++) {
int minW = INT_MAX, now = -1;
for(int j = 0; j < n; j++) {
if(!visit[j] && lowCost[j] <= minW) {
minW = lowCost[j];
now = j;
}
}
if(now != -1) {
sum += minW;
visit[now] = true;
if(i == 1) parent[now] = s;
cout << parent[now] << " " << now << " " << minW << endl;
}
for(int j = 0; j < n; j++) {
if(!visit[j] && adjmat[now][j] <= lowCost[j]) {
lowCost[j] = adjmat[now][j];
parent[j] = now;
}
}
}
}
|
堆优化：
Kruskal算法
非常简单，从权值小到大枚举边，如果构成环就不能加入MST，否则就加入MST。
我们可以快速排序，按照边权值从小到大排序。而判断形成环的步骤可以交给并查集处理。
暴力解法：
带路径输出只需要在最外层循环加一条cout即可：
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
| struct Edge{
int u, v, w;
}edge;
void kruskal() {
int sum = 0;
sort(edge.begin(), edge.end(), [](Edge e1, Edge e2) {
return e1.w < e2.w;
});
for(int i = 0; i < parent.size(); i++) parent[i] = i;
for(auto &i : edge) {
int p = find(mm[i.u]), q = find(mm[i.v]);
if(p != q) {
parent[p] = q;
sum += i.w;
res.push_back({i.u, i.v, i.w});
}
}
if(res.size() -1 != parent.size()) cout << -1 << endl;
else {
cout << sum << endl;
for(auto i : res) {
cout << i.u << " " << i.v << " " << i.w << endl;
}
}
}
|