首页 / 算法 / Kruskal算法

Kruskal算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Kruskal算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含959字，纯文字阅读大概需要2分钟。

内容图文

步骤：

  1. 新建图G，G中拥有原图中相同的节点，但没有边
  2. 将原图中所有的边按权值从小到大排序
  3. 从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中
  4. 重复3，直至图G中所有的节点都在同一个连通分量中

 

技术分享图片

 

技术分享图片

 

 

 

             1 #include<bits/stdc++.h>
 2 3usingnamespace std;
 4 5struct node{
 6int x,y,w;
 7 }a[200002];
 8 9int f[200002];
1011bool cmp(node xx,node yy){//结构体排序12return xx.w<yy.w;
13}
1415int find(int x){
16//并查集说白了就是找父结点的过程，同一个父节点即同一个区间17if(x==f[x]) return x;
18     f[x]=find(f[x]);
19return f[x];
20}
2122int main(){
23int n,k,m=0;
24     scanf("%d",&n);
25for(int i=1;i<=n;i++){
26         f[i]=i;
27for(int j=1;j<=n;j++)
28        {
29             scanf("%d",&k);
30if(j>i){
31//读入时加一个判断就可以了，不需要读那么多32                 m++;
33                 a[m].x=i;a[m].y=j;a[m].w=k; 
34            }   
35        }
36    }
37     sort(a+1,a+m+1,cmp);//排序38int ans=0,p=1;
39for(int i=1;i<=m;i++){
40if(find(a[i].x)!=find(a[i].y)){
41//如果不在一个集合42             ans+=a[i].w;
43             f[find(a[i].x)]=a[i].y;
44//合并两个节点45             p++;
46if(p==n) break; 
47        }
48    }
49     cout<<ans;
50return0;
51 }

 

原文：https://www.cnblogs.com/speedsnail/p/11514957.html

内容总结

以上是互联网集市为您收集整理的Kruskal算法全部内容，希望文章能够帮你解决Kruskal算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1242114.html

来源：【匿名】