首页 > 代码库 > 图论-最小生成树-Kruskal算法
图论-最小生成树-Kruskal算法
有关概念：
最小生成树：在连通图G中，连接图G所有顶点且总权最小的边构成的树
思路：
首先对边按权从小到大排序，紧接着枚举每一条边，如果两个结点的祖先结点不同（并查集），则连上此边，直到边数等于结点数-1即可
邻接矩阵输入，用类邻接表存储方式存边
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define MAXN 5 #define MAXM 6 int father[MAXN],n,m,cnt,ans,a,b; 7 struct node 8 { 9 int u,v,val;10 }edge[MAXM];11 int cmp(node a,node b)12 {13 return a.val<b.val;14 }15 int find(int x)//并查集+路径压缩16 {17 if(father[x]==x)return x;18 else return father[x]=find(father[x]); 19 }20 int main()21 {22 scanf("%d",&n);23 for(int i=1;i<=n;i++)24 father[i]=i;25 for(int i=1;i<=n;i++)26 {27 for(int j=1;j<=n;j++)28 {29 scanf("%d",&a);30 if(a==0)continue;31 edge[++cnt].u=i;32 edge[cnt].v=j;33 edge[cnt].val=a;34 }35 }36 sort(edge+1,edge+cnt+1,cmp);37 m=cnt;38 cnt=1;39 for(int i=1;i<=m;i++)40 {41 a=find(edge[i].u);42 b=find(edge[i].v);43 if(a==b)continue;44 else//连边45 {46 father[b]=a;47 cnt++;48 ans+=edge[i].val;49 if(cnt==n)break;50 }51 }52 printf("%d",ans);//最小生成树权值和53 return 0;54 }
*参考：
http://baike.baidu.com/link?url=kGlXMlnImpXrmDw8uojP7JDeRsPUoZE4YYXNvANyAnfp6cDaQRxkoGV5DY20BU2_ZkkN5TF8ip-djtE5nQ2Lfq
http://baike.baidu.com/link?url=w9DUdZ7x1mt5N8865ZFlthXcYL_LHQU1gOPN8LTEIJVAnu-JO68eL4Oz6zbpmAVa
图论-最小生成树-Kruskal算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。