最小生成树算法

给定图$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;
}
}
}
Author

InverseDa

Posted on

2021-03-22

Updated on

2023-03-30

Licensed under

Comments

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×