欢迎来到天天文库
浏览记录
ID:52793889
大小:112.00 KB
页数:14页
时间:2020-03-30
《用Kruskal算法求无向图的最小生成树.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、用Kruskal算法求无向图的最小生成树该图用邻接矩阵表示,邻接表原理与之相同。可以指出的是,对于有向图,算法可以做得更加简单,因为对无向图的“回边”情况的处理比有向图回边情况的处理要复杂一些。图1:输入示例图二:输入时若两点之间没有公共边,则将权值设置为-1。程序设置处理的最大点数为10。图三:注意到Kruskal算法的解答结果有时候不是唯一的,这个结果和对图遍历时的顺序有关,但是必需注意的是所有的最小生成树其网络代价和是一样的。下面是源代码:/*Kruskal.c Copyright(c)2002,2006byctu
2、_85AllRightsReserved.*//*Iamsorrytosaythatthesituationofunconnectedgraphisnotconcerned*/#include"stdio.h"#definemaxver10#definemaxright100intG[maxver][maxver],record=0,touched[maxver][maxver];intcircle=0;intFindCircle(int,int,int,int);intmain(){intpath[maxver][2]
3、,used[maxver][maxver];inti,j,k,t,min=maxright,exsit=0;intv1,v2,num,temp,status=0;restart:printf("Pleaseenterthenumberofvertex(s)inthegraph:");scanf("%d",&num);if(num>maxver
4、
5、num<0){printf("Error!Pleasereinput!");gotorestart;}for(j=0;j6、+){if(j==k){G[j][k]=maxright;used[j][k]=1;touched[j][k]=0;}elseif(j=maxright7、8、temp<-1){printf("Invalidinput!");gotore;}if(temp==-1)te9、mp=maxright;G[j][k]=G[k][j]=temp;used[j][k]=used[k][j]=0;touched[j][k]=touched[k][j]=0;}}for(j=0;j10、++){for(j=0;j11、ath[t][0]);if(circle){/*ifacircleexsits,rollback*/circle=0;i--;exsit=0;touched[v1][v2]=0;touched[v2][v1]=0;min=maxright;}else{record++;min=maxright;}}}if(!status)printf("Wecannotdealwithitbecausethegraphisnotconnected!");else{for(i=0;i12、vertex%dtovertex%d",i+1,path[i][0]+1,path[i][1]+1);}return1;}intFindCircle(intstart,intbegin,inttimes,intpre){/*tojudgewhetheracircleisproduced*/inti;for(i=0
6、+){if(j==k){G[j][k]=maxright;used[j][k]=1;touched[j][k]=0;}elseif(j=maxright
7、
8、temp<-1){printf("Invalidinput!");gotore;}if(temp==-1)te
9、mp=maxright;G[j][k]=G[k][j]=temp;used[j][k]=used[k][j]=0;touched[j][k]=touched[k][j]=0;}}for(j=0;j10、++){for(j=0;j11、ath[t][0]);if(circle){/*ifacircleexsits,rollback*/circle=0;i--;exsit=0;touched[v1][v2]=0;touched[v2][v1]=0;min=maxright;}else{record++;min=maxright;}}}if(!status)printf("Wecannotdealwithitbecausethegraphisnotconnected!");else{for(i=0;i12、vertex%dtovertex%d",i+1,path[i][0]+1,path[i][1]+1);}return1;}intFindCircle(intstart,intbegin,inttimes,intpre){/*tojudgewhetheracircleisproduced*/inti;for(i=0
10、++){for(j=0;j11、ath[t][0]);if(circle){/*ifacircleexsits,rollback*/circle=0;i--;exsit=0;touched[v1][v2]=0;touched[v2][v1]=0;min=maxright;}else{record++;min=maxright;}}}if(!status)printf("Wecannotdealwithitbecausethegraphisnotconnected!");else{for(i=0;i12、vertex%dtovertex%d",i+1,path[i][0]+1,path[i][1]+1);}return1;}intFindCircle(intstart,intbegin,inttimes,intpre){/*tojudgewhetheracircleisproduced*/inti;for(i=0
11、ath[t][0]);if(circle){/*ifacircleexsits,rollback*/circle=0;i--;exsit=0;touched[v1][v2]=0;touched[v2][v1]=0;min=maxright;}else{record++;min=maxright;}}}if(!status)printf("Wecannotdealwithitbecausethegraphisnotconnected!");else{for(i=0;i12、vertex%dtovertex%d",i+1,path[i][0]+1,path[i][1]+1);}return1;}intFindCircle(intstart,intbegin,inttimes,intpre){/*tojudgewhetheracircleisproduced*/inti;for(i=0
12、vertex%dtovertex%d",i+1,path[i][0]+1,path[i][1]+1);}return1;}intFindCircle(intstart,intbegin,inttimes,intpre){/*tojudgewhetheracircleisproduced*/inti;for(i=0
此文档下载收益归作者所有