Kruskal算法 (克鲁斯卡尔)

《Kruskal算法 (克鲁斯卡尔)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最小生成树的Kruskal算法#include#include#include#defineN300structnode{intx;inty;intvalue;};intfather[N];intcmp(constvoid*a,constvoid*b){return((structnode*)a)->value>((structnode*)b)->value?1:-1;}intfind(intx){inti,j;i=x;while(x!=father[x])x=father[x];while(i!=x)

2、//路径压缩{j=father[i];father[i]=x;i=j;}returnx;}intunoin1(inta,intb){intf1,f2;f1=find(a);f2=find(b);if(f1==f2)return0;else{father[f1]=f2;return1;}}intmain(){inti,j,k;intn,m;intsum;intss;intflag;structnodeedge[N];while(scanf("%d%d",&n,&m)!=EOF){sum=0;ss=0;flag=0;for(i=0;i<=n;i++)father[

3、i]=i;for(i=1;i<=m;i++)scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].value);qsort(edge+1,m,sizeof(edge[0]),cmp);for(i=1;i<=m;i++){if(unoin1(edge[i].x,edge[i].y)){sum+=edge[i].value;ss++;printf("%d--->%d=======%d",edge[i].x,edge[i].y,edge[i].value);}if(ss==n-1){flag=1;break;}}if(fla

4、g)printf("%d",sum);elseprintf("dataerro!");}}