Kruskal算法

      K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。

克鲁斯卡尔算法

　　假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

      

C代码实现

　　/* 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 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;

　　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)

　　{

　　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)

　　{

　　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;

　　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;

　　}

　　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])

　　{

　　used[v1][v2]=1;

　　used[v2][v1]=1;

　　touched[v1][v2]=1;

　　touched[v2][v1]=1;

　　path[0]=v1;

　　path[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;

　　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");

　　else

　　{

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

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

　　{

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

　　{

　　circle=1;

　　return 1;

　　break;

　　}

　　else

　　if(pre!=i)

　　FindCircle(start,i,times,begin);

　　else

　　continue;

　　}

　　return 1;

　　}