数据结构-最小生成树的生成

最小生成树的生成

定义:把无向图的全部n个顶点和n-1条边构成的生成树,其边的权值最小的树称为该图的最小生成树。

实现方法:

  1. prim方法:从任意一个起点开始,以贪心的策略,每次只选择一个距离当前联通部分最小的点加入生成树,直至所有点都被加入该树为止。
  2. kruskal方法:首先把所有的边按权重从小到大排序,然后从权重最小的边开始添加,只要不会形成环就添加这条边,直到所有的点都连接起来。

Prim方法

image-20240605185023203

首先,我们需要任意选择一个起点,这里选节点1作为起点。dist[1] = 0,其余的dist全为0x3f

然后,从所有节点的dist数组里面找到最小的节点加到联通部分。

更新所有与该节点相连的点的dist数组。

一次更新过程如下图所示

image-20240605191803958

下一次更新:

image-20240605192122070

下面是代码实现:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# include <iostream>
# include <cstring>
# include <algorithm>

using namespace std;
const int N = 510;
int g[N][N];//存储图
int dist[N];//存储每个节点到当前联通部分的距离
int state[N];//存储每个点是否被加入联通部分中
int pre[N];//每个点联通时的前置节点
int n,m;

void getpath(){
int res = 0;
//先将所有节点的前置节点置-1
memset(pre, -1, sizeof(pre));
memset(dist, 0x3f, sizeof(dist));
//将1节点的距离置0
dist[1] = 0;

for(int t= 0; t<n; t++){
//查找所有节点中距离联通部分最近的点,加入联通部分
int midist = 0x3f;
int index = -1;
//设置t=-1是为了保留孤立点
for(int i=1; i<=n; i++){
if((index==-1 || dist[i]<dist[index]) && state[i]==0){
midist = dist[i];
index = i;
}

}
//如果是孤立点 无法产生最小生成树
if(dist[index] == 0x3f3f3f3f){
cout<<"impossible"<<endl;
return;
}
//此时找到index节点,将其加入联通部分
state[index] = 1;
//cout<<"index: "<<index<<" midist: "<<midist<<endl;
res += midist;
//更新所有与indx节点相连的点 到联通部分的距离
for(int i=1; i<=n; i++){
//cout<<"dist[i]"<<dist[i]<<" g[i][index]"<<g[i][index]<<endl;
if(state[i]==0 && (dist[i] > g[i][index])){
dist[i] = min(dist[i], g[i][index]);
//cout<<"i: "<<i<<"dist[i]"<<dist[i]<<endl;

}
}

}
cout<<res<<endl;




}

int main(){

memset(g, 0x3f, sizeof(g));

cin>>n>>m;
int a,b,w;
for(int i=0; i<m; i++){
cin>>a>>b>>w;
g[a][b] = g[b][a] =min(w, g[a][b]);
}

getpath();



}

kruskal方法

方法:将所有边按从小到大的顺序排序,一条一条边的尝试加入结果集,如果正在尝试加入的这条边加入后会产生环路,则放弃该边,选择下一条边,直至选完n-1条边。

image-20240605202553078

判断环路产生:使用并查集的方法。使用一个代表数组存储数据,如p=[0,0,0,3,3]的意思是原数组a[0]=a[1]=a[2],他们的代表元素是a[0];a[3]=a[4],他们的代表元素是a[3]。

  1. :如把[1,2,3]和[4,5]合并,只需要把p数组的p[3]修改成0即可
  2. :修改后,如果想查a[4],通过查找p数组,发现a[4]=a[3], 再查找p数组a[3]= a[0],由此就查到了a[4]= a[0]
1
2
3
4
5
6
7
8
9
10
# 找到a的代表元素
# p[0,0,0,1,3] 如果想找到4的代表元素,p[4]= p[3]=p[1]=p[0]
int find(a)
{
if(a!=p[a])
{
return find(p[a]);
}
return p[a];
}

代码实现:

边的存储:使用结构体struct E{int a, b, w;}

排序边:构造compare(const E & a, const E & b)函数比较

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# include <iostream>
# include <algorithm>
# include <cstring>

using namespace std;

struct Edge{
int a,b,w;
}edg[200010];

int p[200010];
int n,m;

bool compare(Edge a, Edge b){
return a.w < b.w;
}

int findp(int a){
if(a != p[a]){
p[a] = findp(p[a]);
}
return p[a];
}

void kruskal(){
int res = 0;
int cnt =0 ;
for(int i =1; i<=m; i++){
int pa = findp(edg[i].a);
int pb = findp(edg[i].b);
if(pa!=pb){
res += edg[i].w;
p[pa] = pb;
cnt ++;

}


}

if(cnt<n-1){
cout<<"impossible"<<endl;

}
else {
cout<<res<<endl;

}
}


int main(){
cin>>n>>m;

for(int i=1; i<=m; i++){
p[i] = i;
}

for(int i=1; i<=m; i++){
cin>>edg[i].a>>edg[i].b>>edg[i].w;
}

sort(edg+1, edg+m+1, compare);

kruskal();


}

数据结构-最小生成树的生成
https://wendyflv.github.io/2024/06/05/数据结构-最小生成树的生成/
作者
Wendyflv
发布于
2024年6月5日
许可协议