Kruscal(最小生成树)算法模版

简介: 1 const int maxn=400;//最大点数 2 const int maxm=10000;//最大边数 3 int n,m;//n表示点数,m表示边数 4 struct edge{int u,v,w;} e[maxm];//u,v,w分别表示该边的两个顶点和权值 5 bool cmp(edge a,edge b) 6 { 7 return a.
 1 const int maxn=400;//最大点数
 2 const int maxm=10000;//最大边数
 3 int n,m;//n表示点数,m表示边数
 4 struct edge{int u,v,w;} e[maxm];//u,v,w分别表示该边的两个顶点和权值
 5 bool cmp(edge a,edge b)
 6 {
 7     return a.w<b.w;
 8 }
 9 int fa[maxn];//因为需要用到并查集来判断两个顶点是否属于同一个连通块
10 int find(int x)
11 {
12     if(x==fa[x]) return x;
13     else return fa[x]=find(fa[x]);
14 }
15 int kruscal()
16 {
17     int ans=-1;
18     sort(e+1,e+1+m,cmp);
19     for(int i=1;i<=n;++i) fa[i]=i;//初始化并查集
20     int cnt=n;
21     for(int i=1;i<=m;++i)
22     {
23         int t1=find(e[i].u);
24         int t2=find(e[i].v);
25         if(t1!=t2)
26         {
27             if(cnt==1) break;
28             fa[t1]=t2;
29             ans=max(ans,e[i].w);
30             cnt--;
31         }
32     }
33     return ans;
34 }

 

目录
相关文章
|
10月前
|
算法 搜索推荐
Kruskal算法
Kruskal算法
|
存储 算法 C++
最小生成树问题及Kruskal算法的解析
最小生成树问题及Kruskal算法的解析
203 2
|
算法
Prim算法和Kruskal算法到底哪个好?
Prim算法和Kruskal算法到底哪个好?
185 0
|
算法 C语言
最小生成树——Prim算法与Kruskal算法
最小生成树——Prim算法与Kruskal算法
352 0
最小生成树——Prim算法与Kruskal算法
kruskal算法的实现
kruskal算法的实现
prim算法的实现
prim算法的实现
|
算法 C++
算法模版:暴力搜索之BFS
算法模版:暴力搜索之BFS
算法模版:暴力搜索之BFS
算法模版:暴力搜索之DFS
算法模版:暴力搜索之DFS
下一篇
无影云桌面