Kruskal算法

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

　　scanf("%d",&num);

　　if(num>maxver||num<0)

　　{

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

　　goto restart;

　　}

　　for(j=0;j

　　for(k=0;k

　　{

　　if(j==k)

　　{

　　G[j][k]=maxright;

　　used[j][k]=1;

　　touched[j][k]=0;

　　}

　　else

　　if(j

　　{

　　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

　　{

　　path[j][0]=0;

　　path[j][1]=0;

　　}

　　for(j=0;j

　　{

　　status=0;

　　for(k=0;k

　　if(G[j][k]

　　{

　　status=1;

　　break;

　　}

　　if(status==0)

　　break;

　　}

　　for(i=0;i

　　{

　　for(j=0;j

　　for(k=0;k

　　if(G[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

　　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

　　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

　　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

　　}

　　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

　　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

　　if i

　　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

　　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.