最小生成树Kruscal算法 | Eternal_zttz

最小生成树Kruscal算法

Kruscal 算法是另一种计算最小生成树的算法。

基本算法思想如下:

  1. 建立图,其中有n个顶点,m条边。
  2. 将所有的边按照权值从小到大排序。
  3. 从权值最小的边开始,依次选取边,如果选的边与之前已选的边之间不构成环,那么将此条边加入到最小生成树的集合中,否则,若构成环,跳过该边,选择下一条继续判断。
  4. 依次选取边,直到选取到n-1条边,此时所有的边和顶点构成的即是最小生成树。
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
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define MaxN 200005 //边的最大数目
#define Maxver 5005 //顶点的最大数目
struct Edge{
int u,v,w;//u为边的起点,v为边的终点,w为边的权值
bool operator < (const Edge&a)const{//重载小于符号,用于边按照权值排序
return w<a.w;
}
}edge[MaxN];
int fa[Maxver],n,m,ans,eu,ev,cnt;
//判断是否构成环的函数,这个函数是为了找到树的根节点,如果新加入的边能够构成环,说明两个点u,v之前都在最小生成树里,那么find(u) == find(v),因为根节点相同。否则,新加入的边不构成环。
int find(int x){
return x == fa[x]? x:find(fa[x]);
}
void kruskal(){
sort(edge,edge+m);
for( int i=0;i<m;i++){
eu=find(edge[i].u);
ev=find(edge[i].v);
if(eu==ev)//如果eu==ev说明新加入的边已经构成环了
continue;
ans+=edge[i].w;
fa[ev]=eu;
if(++cnt==n-1)
break;
}
}
int main(){
scanf("%d %d",&n,&m);
for( int i=1;i<=n;i++)
fa[i]=i;//初始化根节点
for( int i=0;i<m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
edge[i] = {u,v,w};
//相当于scanf("%d %d %d",&edge[i].u,&edge[i].v,&edge[i].w);
}
kruskal();
printf("%d\n",ans);
return 0;
}
-------------The End-------------