kruskal 算法
假设给定一个加权连通图g，g的边集合为e，顶点个数为n，要求其一棵最小生成树t。
kruskal 算法的粗略描述：
假设t中的边和顶点均涂成红色，其余边为白色。开始时g中的边均为白色。
1）将所有顶点涂成红色；
2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红；
3）重复2）直到有n-1条红色边，这n-1条红色边便构成最小生成树t的边集合。
注意到在算法执行过程中，红色顶点和红色边会形成一个或多个连通分支，它们都是g的子树。一条边与红色边形成圈当且仅当这条边的两个端点属于同一个子树。因此判定一条边是否与红色边形成圈，只需判断这条边的两端点是否属于同一个子树。
上述判断可以如此实现：给每个子树一个不同的编号，对每一个顶点引入一个标记t，表示这个顶点所在的子树编号。当加入一条红色边，就会使该边两端点所在的两个子树连接起来，成为一个子树，从而两个子树中的顶点标记要改变成一样。综上，可将kruskal算法细化使其更容易计算机实现。
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=0,j=0,k=0,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<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;
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<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)
{
if(i==start&&pre!=start)
{
circle=1;
return 1;
break;
}
else
if(pre!=i)
findcircle(start,i,times,begin);
else
continue;
}
return 1;
}