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

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

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

该图用邻接矩阵表示，邻接表原理与之相同。可以指出的是，对于有向图，算法可以做得更加简单，因为对无向图的“回边”情况的处理比有向图回边情况的处理要复杂一些。

图1：输入示例

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

图二：输入时若两点之间没有公共边，则将权值设置为-1。程序设置处理的最大点数为10。

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

图三：注意到Kruskal算法的解答结果有时候不是唯一的，这个结果和对图遍历时的顺序有关，但是必需注意的是所有的最小生成树其网络代价和是一样的。

下面是源代码：

/* Kruskal.c

Copyright (c) 2002, 2006 by ctu_85

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

All Rights Reserved.

*/

/* I am sorry to say that the situation of unconnected graph

#include "stdio.h"

#define maxver 10

#define maxright 100

int G[maxver][maxver],record=0,touched[maxver][maxver];

int circle=0;

int FindCircle(int,int,int,int);

int main()

{

int path[maxver][2],used[maxver][maxver];

int i,j,k,t,min=maxright,exsit=0; is not concerned */

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

int v1,v2,num,temp,status=0;

restart:

printf("Please enter the number of vertex(s) in the graph:\n");

scanf("%d",&num);

if(num>maxver||num<0)

{

printf("Error!Please reinput!\n");

goto restart;

}

for(j=0;j<num;j++)

for(k=0;k<num;k++)

{

if(j==k)

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

{

G[j][k]=maxright;

used[j][k]=1;

touched[j][k]=0;

}

else

if(j<k)

{

re:

printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1); scanf("%d",&temp);

if(temp>=maxright||temp<-1)

{

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

printf("Invalid input!\n");

goto re;

}

if(temp==-1)

temp=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;j<num;j++)

{

path[j][0]=0;

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

path[j][1]=0;

}

for(j=0;j<num;j++)

{

status=0;

for(k=0;k<num;k++)

if(G[j][k]<maxright)

{

status=1;

break;

}

if(status==0)

break;

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

}

for(i=0;i<num-1&&status;i++)

{

for(j=0;j<num;j++)

for(k=0;k<num;k++)

if(G[j][k]<min&&!used[j][k])

{

v1=j;

v2=k;

min=G[j][k];

}

if(!used[v1][v2])

{

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

used[v1][v2]=1;

used[v2][v1]=1;

touched[v1][v2]=1;

touched[v2][v1]=1;

path[i][0]=v1;

path[i][1]=v2;

for(t=0;t<record;t++)

FindCircle(path[t][0],path[t][0],num,path[t][0]);

if(circle)

{/*if a circle exsits,roll back*/

circle=0;

i--;

exsit=0;

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

touched[v1][v2]=0;

touched[v2][v1]=0;

min=maxright;

}

else

{

record++;

min=maxright;

}

}

}

if(!status)

printf("We cannot deal with it because the graph is not connected!\n");

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

else

{

for(i=0;i<num-1;i++)

printf("Path %d:vertex %d to vertex %d\n",i+1,path[i][0]+1,path[i][1]+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;i<times;i++)

if(touched[begin][i]==1)

{

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

if(i==start&&pre!=start) {

circle=1;

return 1;

break;

}

else

if(pre!=i)

FindCircle(start,i,times,begin); else

continue;

}

return 1;

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

}