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 }

 

目录
相关文章
|
4月前
|
存储 算法 C语言
数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)
数据结构学习记录——图-最短路径问题(无权图单源最短路径算法、有权图单源最短路径算法、多源最短路径算法、Dijkstra(迪杰斯特拉)算法、Floyd算法)
60 1
|
5月前
|
NoSQL 容器 消息中间件
图、图的遍历及图的拓扑排序
图、图的遍历及图的拓扑排序
|
存储 算法 C++
最小生成树问题及Kruskal算法的解析
最小生成树问题及Kruskal算法的解析
205 2
|
Cloud Native 算法 Go
886. 可能的二分法:图+深度优先算法
这是 力扣上的 886. 可能的二分法,难度为 中等。
|
算法 容器
【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树(下)
【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树
104 0
|
存储 算法 UED
【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树(上)
【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树
76 0
|
算法
设计算法求无向图的深度优先生成树
设计算法求无向图的深度优先生成树
83 0
|
存储 算法
树与图的存储算法模板
树与图的存储算法模板
77 0
下一篇
无影云桌面