一种简单的计算机编码

Kruskal 算法

Kruskal 算法的粗略描述

C代码

C++代码

pascal 例程

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;

}

C++代码

#include<iostream>

#include<queue>

using namespace std;

struct EdgeNode

{

int v1;

int v2;

int value;

bool operator<(const EdgeNode &a) const

{

return a.value<value;

}

};

int *root;

priority_queue<EdgeNode> pq;

int Find(int x)

{

int i=x;

while(i!=root[i])

i=root[i];

while(i!=root[x])

{

temp=root[x];

root[x]=i;

x = temp;

}

return i;

}

void Union(int a,int b)

{

a=Find(a);

b=Find(b);

if(a!=b)

root[a]=b;

}

void Kruskal()

{

EdgeNode b;

cout<<"加入最小生成树中的边依次为: "<<endl;

while(!pq.empty())

{

b=pq.top();

pq.pop();

if(Find(b.v1)!=Find(b.v2))

{

cout<<b.v1<<"----"<<b.v2<<endl;

Union(b.v1,b.v2);

}

}

}

void main()

{

int n=0;

int m=0;

cout<<"请输入图中点的个数: "<<endl;

cin>>n;

root=new int [n+1];

for(int i=1;i<=n;i++)

root[i]=i;

cout<<"请输入图中边的条数: "<<endl;

cin>>m;

EdgeNode a;

cout<<"请依次输入每条边的两个顶点及其权重: "<<endl;

while(m--)

{

cin>>a.v1>>a.v2>>a.value;

pq.push(a);

}

Kruskal();

}

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]:= 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要加入并查集,判断点是否在同一个集合内,

如果在则不能取该边!

只适用与稀疏图