Kruskal

求加權連通圖最小生成樹的演演算法

Kruskal是求加權連通圖的最小生成樹的演演算法。

目錄
1描述 2代碼 3解決實際問題

描述

假設給定一個加權連通圖G，G的邊集合為E，頂點個數為n，要求其一棵最小生成樹T。
假設T中的邊和頂點均塗成紅色，其餘邊為白色。開始時G中的邊均為白色。
1）將所有頂點塗成紅色；
2）在白色邊中，挑選一條權最小的邊，使其與紅色邊不形成圈，將該白色邊塗紅；
3）重複2）直到有n-1條紅色邊，這n-1條紅色邊便構成最小生成樹T的邊集合。
注意到在演演算法執行過程中，紅色頂點和紅色邊會形成一個或多個連通分支，它們都是G的子樹。一條邊與紅色邊形成圈當且僅當這條邊的兩個端點屬於同一個子樹。因此判定一條邊是否與紅色邊形成圈，只需判斷這條邊的兩端點是否屬於同一個子樹。
上述判斷可以如此實現：給每個子樹一個不同的編號，對每一個頂點引入一個標記t，表示這個頂點所在的子樹編號。當加入一條紅色邊，就會使該邊兩端點所在的兩個子樹連接起來，成為一個子樹，從而兩個子樹中的頂點標記要改變成一樣。綜上，可將Kruskal演演算法細化使其更容易計算機實現。
上面的方法其實就是不相交集的一種應用，不相交集數據結構提供兩種操作Find和Union，通過Find操作來查看挑選的邊得兩個頂點是否屬於同一子樹，如果不屬於則將此邊放入T中，且對兩子樹執行Union操作：
有關Find和Union的具體代碼實現和解決Kruskal去環的詳細內容請查看不相交集。
Kruskal演演算法的時間複雜度由排序演演算法決定，若採用快速排序演演算法則時間複雜度為O(N log N)。

代碼

C
#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:\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)
{
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)
{
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;
}
C++
#include
#include
using namespace std;
struct EdgeNode
{
int v1;
int v2;
int value;
bool operator<(const EdgeNode &a) const
{
return a.value
}
};
int *root;
priority_queue 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<<"加入最小生成樹中的邊依次為: "<
while(!pq.empty())
{
b=pq.top();
pq.pop();
if(Find(b.v1)!=Find(b.v2))
{
cout<
Union(b.v1,b.v2);
}
}
}
void main()
{
int n=0;
int m=0;
cout<<"請輸入圖中點的個數: "<
cin>>n;
root=new int [n+1];
for(int i=1;i<=n;i++)
root[i]=i;
cout<<"請輸入圖中邊的條數: "<
cin>>m;
EdgeNode a;
cout<<"請依次輸入每條邊的兩個頂點及其權重: "<
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!
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要加入並查集,判斷點是否在同一個集合內,
如果在則不能取該邊!
只適用於稀疏圖

解決實際問題

NOIP2013 提高組 貨車運輸

基本信息

用途
求加權連通圖
屬性
演算法
概念
求加權連通圖的最小生成樹的演算法
  • 目錄