§ 基本资料

1. Kruskal算法

(1) 算法思想

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

初始时没有任何边被选择。边（ 1 , 6）是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。下一步选择边（ 3，4）并将其加入树中（如图1 3 - 1 2 d所示）。然后考虑边( 2，7 ，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。下一步考虑边（ 2，3）并将其加入树中（如图1 3 - 1 2 f所示）。在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（ 5，4）加入树中，得到的树如图13-12g 所示。下一步考虑边（ 7，5），由于会产生环路，将其丢弃。最后考虑边（ 6，5）并将其加入树中，产生了一棵生成树，其耗费为9 9。图1 - 1 3给出了K r u s k a l算法的伪代码。

(2)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:\");

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;

}

（3）pascal代码

{

最小生成树的Kruskal算法。

Kruskal算法基本思想：

每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量

排序使用Quicksort(O(eloge))

检查是否在同一连通分量用Union-Find，每次Find和union运算近似常数

Union-Find使用rank启发式合并和路径压缩

总复杂度O(eloge)=O(elogv) (因为e<n(n-1)/2)

}

const

maxn=100;

maxe=maxn*maxn;

type

edge=record

a,b    :integer;  　  //边的2个顶点

len    :integer;  　  //边的长度

end;

var

edges :array【0..maxe】of edge;    //保存所有边的信息

p,r   :array【0..maxn】of integer;   //p保存i的父亲节点，r用来实现Union-Find的rank启发式

n,e   :integer;  　 //n为顶点数，e为边数

procedure swap(a,b:integer);    //交换

begin

edges【0】:=edges【a】;

edges【a】:=edges;

edges:=edges【0】;

end;

procedure quicksort(l,r:integer);   //快速排序

var

x,i,j :integer;

begin

x:=edges【random(r-l+1)+l】.len;

i:=l;j:=r;

repeat

while edges.len<x do inc(i);

while edges【j】.len>x do dec(j);

if i<=j then

begin

swap(i,j);

inc(i);dec(j);

end

until i>j;

if l<j then quicksort(l,j);

if i<r then quicksort(i,r);

end;

procedure init;

var

i  　 :integer;

begin

assign(input,'g.in');reset(input);

readln(n,e);

for i:=1 to e do readln(edges.a,edges.b,edges.len);　//从文件读入图的信息

for i:=1 to n do p:=i;   //初始化并查集

randomize;

quicksort(1,e);  　  //使用快速排序将边按权值从小到大排列

end;

function find(x:integer):integer;  　 //并查集的Find，用来判断2个顶点是否属于一个连通分量

begin

if x<>p【x】 then p【x】:=find(p【x】);

find:=p【x】

end;

procedure union(a,b:integer);  　 //如果不属于且权值最小则将2个顶点合并到一个连通分量

var

t  　 :integer;

begin

a:=find(a);b:=find(b);

if r【a】>r then begin t:=a;a:=b;b:=t end;

if r【a】=r then inc(r);

p【a】:=b;

end;

procedure kruskal;  　  //主过程

var

en    :integer;   //en为当前边的编号

count :integer;   //统计进行了几次合并。n-1次合并后就得到最小生成树

tot   :integer;   //统计最小生成树的边权总和

begin

count:=0;en:=0; tot:=0;

while count<n-1 do

begin

inc(en);

with edges【en】 do

begin

if find(a)<>find(b) then

begin

union(a,b);

writeln(a,'--',b,':',len);

inc(tot,len);

inc(count);

end;

end;

end;

writeln('Total Length=',tot)

end;

{===========main==========}

begin

init;

kruskal;

end.

§ 相关条目

程序　　　　　 代码

• 宁德市
• 宁德春
• 宁德林烈士
• 宁德标烈士
• 宁德财烈士
• 宁德霍童线狮
• 宁心
• 宁心宝胶囊
• 宁志膏
• 宁忠汉
• 宁息
• 宁懋石室画像
• 宁成
• 宁戚叩牛
• 宁戚歌
• 宁才
• 宁折不弯
• 宁振邦烈士
• 宁敬武
• 宁方
• 宁方颜烈士
• 宁时发烈士
• 宁昌
• 宁明中学
• 宁明县