“Kruskal”的意思、由来-中文百科全书

词条

Kruskal

释义

§ Kruskal 算法

假设给定一个加权连通图G，G的边集合为E，顶点个数为n，要求其一棵最小生成树T。

Kruskal 算法的粗略描述：

假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。

1）将所有顶点涂成红色；

2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红；

3）重复2）直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。

注意到在算法执行过程中，红色顶点和红色边会形成一个或多个连通分支，它们都是G的子树。一条边与红色边形成圈当且仅当这条边的两个端点属于同一个子树。因此判定一条边是否与红色边形成圈，只需判断这条边的两端点是否属于同一个子树。

上述判断可以如此实现：给每个子树一个不同的编号，对每一个顶点引入一个标记t，表示这个顶点所在的子树编号。当加入一条红色边，就会使该边两端点所在的两个子树连接起来，成为一个子树，从而两个子树中的顶点标记要改变成一样。综上，可将Kruskal算法细化使其更容易计算机实现。

§ C代码

/*　Kruskal.c

/* 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:\");

scanf("%d",&num);

if(num>maxver||num<0)

{

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

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:\",j+1,k+1);

scanf("%d",&temp);

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

{

printf("Invalid input!\");

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

else

{

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

printf("Path %d:vertex %d to vertex %d\",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;

}

随便看

百科全书收录594082条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。