用Kruskal算法求无向图的最小生成树.doc

用Kruskal算法求无向图的最小生成树该图用邻接矩阵表示，邻接表原理与之相同。可以指出的是，对于有向图，算法可以做得更加简单，因为对无向图的“回边”情况的处理比有向图回边情况的处理要复杂一些。图1：输入示例图二：输入时若两点之间没有公共边，则将权值设置为-1。程序设置处理的最大点数为10。图三：注意到Kruskal算法的解答结果有时候不是唯一的，这个结果和对图遍历时的顺序有关，但是必需注意的是所有的最小生成树其网络代价和是一样的。下面是源代码：/* Kruskal.c Copyright (c) 2002, 2006 by ctu_85 All Rights Reserved.*/* I am sorry to say that the situation of unconnected graph is not concerned */#include stdio.h#define maxver 10#define maxright 100int Gmaxvermaxver,record=0,touchedmaxvermaxver;int circle=0;int FindCircle(int,int,int,int);int main()int pathmaxver2,usedmaxvermaxver;int i,j,k,t,min=maxright,exsit=0;int v1,v2,num,temp,status=0;restart:printf(Please enter the number of vertex(s) in the graph:n);scanf(%d,&num);if(nummaxver|num0)printf(Error!Please reinput!n);goto restart;for(j=0;jnum;j+)for(k=0;knum;k+)if(j=k)Gjk=maxright;usedjk=1;touchedjk=0;elseif(j=maxright|temp-1)printf(Invalid input!n);goto re;if(temp=-1)temp=maxright;Gjk=Gkj=temp;usedjk=usedkj=0;touchedjk=touchedkj=0;for(j=0;jnum;j+)pathj0=0;pathj1=0;for(j=0;jnum;j+)status=0;for(k=0;knum;k+)if(Gjkmaxright)status=1;break;if(status=0)break;for(i=0;inum-1&status;i+)for(j=0;jnum;j+)for(k=0;knum;k+)if(Gjkmin&!usedjk)v1=j;v2=k;min=Gjk;if(!usedv1v2)usedv1v2=1;usedv2v1=1;touchedv1v2=1;touchedv2v1=1;pathi0=v1;pathi1=v2;for(t=0;trecord;t+)FindCircle(patht0,patht0,num,patht0);if(circle)/*if a circle exsits,roll back*/circle=0;i-;exsit=0;touchedv1v2=0;touchedv2v1=0;min=maxright;elserecord+;min=maxright;if(!status)printf(We cannot deal with it because the graph is not connected!n);elsefor(i=0;inum-1;i+)printf(Path %d:vertex %d to vertex %dn,i+1,pathi0+1,pathi1+1);return 1;int FindCircle(int start,int begin,int times,int pre) /* to judge whether a circle is produced*/int i;for(i=0;itimes;i+)if(touchedbegini=1)if(i=start&pre!=star