求加權連通圖的最小生成樹的算法。
基本介紹
- 中文名：克魯斯卡爾
- 外文名：Kruskal
- 概念：求加權連通圖的最小生成樹的算法
- 屬性：算法
- 用途：求加權連通圖
描述,代碼,解決實際問題,
描述
假設T中的邊和頂點均塗成紅色，其餘邊為白色。開始時G中的邊均為白色。
1）將所有頂點塗成紅色；
2）在白色邊中，挑選一條權最小的邊，使其與紅色邊不形成圈，將該白色邊塗紅；
3）重複2）直到有n-1條紅色邊，這n-1條紅色邊便構成最小生成樹T的邊集合。
注意到在算法執行過程中，紅色頂點和紅色邊會形成一個或多個連通分支，它們都是G的子樹。一條邊與紅色邊形成圈若且唯若這條邊的兩個端點屬於同一個子樹。因此判定一條邊是否與紅色邊形成圈，只需判斷這條邊的兩端點是否屬於同一個子樹。
上述判斷可以如此實現：給每個子樹一個不同的編號，對每一個頂點引入一個標記t，表示這個頂點所在的子樹編號。當加入一條紅色邊，就會使該邊兩端點所在的兩個子樹連線起來，成為一個子樹，從而兩個子樹中的頂點標記要改變成一樣。綜上，可將Kruskal算法細化使其更容易計算機實現。
上面的方法其實就是不相交集的一種套用，不相交集數據結構提供兩種操作Find和Union，通過Find操作來查看挑選的邊得兩個頂點是否屬於同一子樹，如果不屬於則將此邊放入T中，且對兩子樹執行Union操作：
if(Find(i)!=Find(j)){inserte(i,j)intoT;Union(Find(i),Find(j),p);}有關Find和Union的具體代碼實現和解決Kruskal去環的詳細內容請查看不相交集。
Kruskal算法的時間複雜度由排序算法決定，若採用快速排序算法則時間複雜度為O(N log N)。
代碼
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:\n");
scanf("%d",&num);
if (num>maxver||num<0)
{
printf("Error!Please reinput!\n");
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:\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<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!\n");
else
{
for (i=0;i<num-1;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<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!
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 提高組 貨車運輸
#include<bits/stdc++.h>using namespace std;const int MAXN=1e4+10;const int MAXM=5e4+10;struct edge{ int to,from,next,v; bool operator<(const edge &r)const{return v<r.v;}}e[MAXM],t[MAXM];priority_queue<edge>q;int n,m,T,head[MAXN],tot=0;void insert(int a,int b,int c){ e[tot].to=b; e[tot].next=head[a]; e[tot].v=c; head[a]=tot++;}int f[MAXM];int find(int x){return f[x]==x?x:f[x]=f[find(f[x])];}int up[MAXN][20],fa[MAXN][20],deep[MAXN];void set_tree(int x){ for(int i=head[x];i!=-1;i=e[i].next) { int y=e[i].to; if(fa[x][0]==y) continue; deep[y]=deep[x]+1; fa[y][0]=x; up[y][0]=e[i].v; for(int i=1;i<=15;++i) fa[y][i]=fa[fa[y][i-1]][i-1],up[y][i]=min(up[y][i-1],up[fa[y][i-1]][i-1]); set_tree(y); }}int query(int u,int v){ if(u==v) return 1e9; if(fa[u][0]==fa[v][0]) return min(up[u][0],up[v][0]); for(int i=15;i>=0;--i) if(fa[u][i]!=fa[v][i]) { int down=min(up[u][i],up[v][i]); return min(down,query(fa[u][i],fa[v][i])); }}int ask(int u,int v){ if(deep[u]==deep[v]) return query(u,v); if(deep[u]<deep[v]) swap(u,v); for(int i=15;i>=0;--i) if(deep[fa[u][i]]>=deep[v]) return min(ask(fa[u][i],v),up[u][i]);}int main(){ ios::sync_with_stdio(0); memset(head,-1,sizeof(head)); cin>>n>>m; for(int i=1;i<=n;++i) f[i]=i; for(int i=1;i<=n;++i) for(int j=0;j<=18;++j) up[i][j]=1e9; for(int i=1,a,b,c;i<=m;++i) cin>>a>>b>>c,q.push((edge){a,b,0,c}); while(!q.empty()) { edge x=q.top(); q.pop(); int a=x.from,b=x.to,c=x.v; f[a]=find(f[a]); f[b]=find(f[b]); if(f[a]!=f[b]) { f[f[a]]=f[b]; insert(a,b,c); insert(b,a,c); } } deep[1]=1; set_tree(1); cin>>T; for(int i=1;i<=n;++i) f[i]=find(f[i]); while(T--) { int a,b; cin>>a>>b; if(f[a]==f[b]) cout<<ask(a,b)<<endl; else cout<<"-1"<<endl; } return 0;}