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:
");
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[b];
edges[b]:=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.
例题详见 vijos p1045 Kerry 的电缆网络
type
rec=record
x,y:longint;
cost:real;
end;
var
f:array[1..1000000] of rec;
s,ans:real;
i,n,m,k,dad:longint;
father:array[1..1000000] of longint;
procedure kp(l,r:longint);
var
i,j:longint;
xx:real;
y:rec;
begin
i:=l;
j:=r;
xx:=f[(i+j) div 2].cost;
repeat
while xx>f[i].cost do inc(i);
while xx<f[j].cost do dec(j);
if i<=j then
begin
y:=f[i];
f[i]:=f[j];
f[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if i<r then kp(i,r);
if l<j then kp(l,j);
end;
function find(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=find(father[x]);
exit(father[x]);
end;
procedure union(x,y:longint;j:real);
begin
x:=find(x);
y:=find(y);
if x<>y then
begin
father[y]:=x;
ans:=ans+j;
inc(k);
end;
end;
begin
readln(s);
readln(n);
m:=0;
while not eof do
begin
inc(m);
with f[m] do
readln(x,y,cost);
end;
if m<n-1 then
begin
writeln('Impossible');
exit;
end;
for i:=1 to n do
father[i]:=i;
kp(1,m);
k:=0;
for i:=1 to m do
begin
if k=n-1 then break;
union(f[i].x,f[i].y,f[i].cost);
end;
if k<n-1 then
begin
writeln('Impossible');
exit;
end;
if ans>s then writeln('Impossible') else
writeln('Need ',ans:0:2,' miles of cable');
end.