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
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
Highlight by yzfy 雨中飞燕
*/
/* 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;
}
pascal 例程USER: BO LIU [raulliu2]
TASK: agrinet
LANG: PASCAL
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0 secs]
Test 2: TEST OK [0 secs]
Test 3: TEST OK [0 secs]
Test 4: TEST OK [0.004 secs]
Test 5: TEST OK [0.004 secs]
Test 6: TEST OK [0 secs]
Test 7: TEST OK [0.004 secs]
Test 8: TEST OK [0.004 secs]
Test 9: TEST OK [0.004 secs]
Test 10: TEST OK [0.012 secs]
All tests OK.
Your program ('agrinet') produced all correct answers! This is your
submission #4 for this problem. Congratulations!
标准MST，啥优化都不要。。刚开始用kruskal做的。。不知道怎么回事老是WA on test5....很郁闷的说。只得改用prim。。。我可不喜欢prim啊。。。。
my ugly code :
PRIM:
{
PROG:agrinet
ID:parachutes
LANG:PASCAL
}
var
map : array[1 .. 100, 1 .. 100] of longint;
d : array[1 .. 100] of longint;
mark : array[1 .. 100] of boolean;
n, i, ans, j : longint;
procedure prim;
var
i, j, min, minj : longint;
begin
fillchar(mark, sizeof(mark), 0);
mark[1] := true;
for i := 1 to n do begin
if map[1, i] <> 0 then d := map[1, i]
else d := maxlongint;
end;
ans := 0;
for i := 2 to n do begin
min := maxlongint;
for j := 1 to n do begin
if (not mark[j]) and (d[j] < min) then begin
min := d[j];
minj := j;
end;
end;
mark[minj] := true;
inc(ans, d[minj]);
for j := 1 to n do
if (d[j] > map[minj, j]) and (map[minj, j] <> 0) then
d[j] := map[minj, j];
end;
end;
begin
assign(input,'agrinet.in'); reset(input);
assign(output,'agrinet.out'); rewrite(output);
readln(n);
for i := 1 to n do begin
for j := 1 to n do
read(map[i, j]);
readln;
end;
prim;
writeln(ans);
close(input); close(output);
end.
===================================强大的分割线====================================
{
PROG:agrinet
ID:parachutes
LANG:PASCAL
}
var
x, j, tot, i, n : longint;
l, a, b : array[1 .. 10000] of longint;
f : array[1 .. 100] of longint;
v : array[1 .. 100, 1 .. 100] of boolean;
procedure qsort(ll, rr : longint);
var
i, j, mid, temp : longint;
begin
i := ll; j := rr; mid := l[(i + j) shr 1];
repeat
while l < mid do inc(i);
while l[j] > mid do dec(j);
if i <= j then begin
temp := l; l := l[j]; l[j] := temp;
temp := a; a := a[j]; a[j] := temp;
temp := b; b := b[j]; b[j] := temp;
inc(i); dec(j);
end;
until i > j;
if i < rr then qsort(i, rr);
if ll < j then qsort(ll, j);
end;
function find(x : longint) : longint;
var
tmp : longint;
begin
if f[x] = x then exit(x)
else exit(find(f[x]));
end;
procedure union(u, v : longint);
var
fu, fv : longint;
begin
fu := find(u);
fv := find(v);
f[fv] := fu;
end;
procedure kruskal;
var
cnt, i, ans : longint;
begin
for i := 1 to n do f := i;
cnt := 0;
ans := 0;
for i := 1 to tot do
if (find(a) <> find(b)) then begin
union(a, b);
ans := ans + l;
inc(cnt);
if cnt = n - 1 then break;
end;
writeln(ans);
end;
begin
assign(input,'agrinet.in'); reset(input);
assign(output,'agrinet.out'); rewrite(output);
fillchar(v, sizeof(v), 0);
tot := 0;
readln(n);
for i := 1 to n do begin
for j := 1 to n do begin
read(x);
if (not v[i, j]) and (i <> j) then begin
inc(tot);
a[tot] := i;
b[tot] := j;
v[i, j] := true;
v[j, i] := true;
l[tot] := x;
end;
end;
readln;
end;
qsort(1, tot);
kruskal;
close(input); close(output);
end.
KRUSKAL要加入并查集,判断点是否在同一个集合内,
如果在则不能取该边!
只适用与稀疏图