反饋

最小生成樹

一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，並且有保持圖連通的最少的邊。^[1] 最小生成樹可以用kruskal（克魯斯卡爾）算法或prim（普里姆）算法求出。

中文名: 最小生成樹
外文名: Minimum Spanning Tree,MST
提出者: Kruskal（克魯斯卡爾）Prim（普里姆）

適用領域: 應用圖論知識的實際問題
應用學科: 計算機，數學（圖論），數據結構
算法: Kruskal算法，Prim算法

最小生成樹概述

在一給定的無向圖G = (V, E) 中，(u, v) 代表連接頂點 u 與頂點 v 的邊（即），而 w(u, v) 代表此邊的權重，若存在 T 為 E 的子集且為無循環圖，使得聯通所有結點的的 w(T) 最小，則此 T 為 G 的最小生成樹。

最小生成樹其實是最小權重生成樹的簡稱。^[1]

圖示

最小生成樹應用

圖示

生成樹和最小生成樹有許多重要的應用。

例如：要在n個城市之間鋪設光纜，主要目標是要使這 n 個城市的任意兩個之間都可以通信，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同，因此另一個目標是要使鋪設光纜的總費用最低。這就需要找到帶權的最小生成樹。^[1]

最小生成樹性質

説明

最小生成樹性質：設G=(V，E）是一個連通網絡，U是頂點集V的一個非空真子集。若(u，v）是G中一條“一個端點在U中（例如：u∈U），另一個端點不在U中的邊（例如：v∈V-U），且（u，v）具有最小權值，則一定存在G的一棵最小生成樹包括此邊（u，v）。

證明

為方便説明，先作以下約定：

①將集合U中的頂點看作是紅色頂點，②而V-U中的頂點看作是藍色頂點，③連接紅點和藍點的邊看作是紫色邊，④權最小的紫邊稱為輕邊（即權重最"輕"的邊）。於是，MST性質中所述的邊（u，v）就可簡稱為輕邊。

用反證法證明MST性質：

假設G中任何一棵MST都不含輕邊（u，v）。則若T為G的任意一棵MST，那麼它不含此輕邊。

根據樹的定義，則T中必有一條從紅點u到藍點v的路徑P，且P上必有一條紫邊（u'，v'）連接紅點集和藍點集，否則u和v不連通。當把輕邊（u，v）加入樹T時，該輕邊和P必構成了一個迴路。刪去紫邊（u'，v'）後迴路亦消除，由此可得另一生成樹T'。

T'和T的差別僅在於T'用輕邊（u，v）取代了T中權重可能更大的紫邊（u'，v'）。因為w(u，v）≤w（u'，v'），所以

w(T')=w(T)+w(u，v)-w(u'，v'）≤w(T)

即T'是一棵比T更優的MST，所以T不是G的MST，這與假設矛盾。

所以，MST性質成立。^[1]

最小生成樹算法描述

求MST的一般算法可描述為：針對圖G，從空樹T開始，往集合T中逐條選擇並加入n-1條安全邊（u，v），最終生成一棵含n-1條邊的MST。

當一條邊（u，v）加入T時，必須保證T∪{(u，v)}仍是MST的子集，我們將這樣的邊稱為T的安全邊。

Prim算法簡述

1).輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；

2).初始化：V_new= {x}，其中x為集合V中的任一節點（起始點），E_new= {},為空；

3).重複下列操作，直到V_new= V：

a.在集合E中選取權值最小的邊<u, v>，其中u為集合V_new中的元素，而v不在V_new集合當中，並且v∈V（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；

b.將v加入集合V_new中，將<u, v>邊加入集合E_new中；

4).輸出：使用集合V_new和E_new來描述所得到的最小生成樹。^[1]

Kruskal算法簡述

假設 WN=(V,{E}) 是一個含有 n 個頂點的連通網，則按照克魯斯卡爾算法構造最小生成樹的過程為：先構造一個只含 n 個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結點，則它是一個含有 n 棵樹的一個森林。之後，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是説，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有 n-1條邊為止。^[1]

偽代碼

GenerieMST(G){//求G的某棵MST

T〈-￠； //T初始為空，是指頂點集和邊集均空

while T未形成G的生成樹 do{

找出T的一條安全邊（u，v）；//即T∪{(u，v)}仍為MST的子集

T=T∪{(u，v)}； //加入安全邊，擴充T

}

return T； //T為生成樹且是G的一棵MST

}

注意：

下面給出的兩種求MST的算法均是對上述的一般算法的求精，兩算法的區別僅在於求安全邊的方法不同。

為簡單起見，下面用序號0，1，…，n-1來表示頂點集，即是：

V(G)={0，1，…，n-1}，

G中邊上的權解釋為長度，並設T=(U，TE）。

C語言代碼

#include<stdio.h>
　#include<stdlib.h>
　#include<iostream.h>
　#defineMAX_VERTEX_NUM20
　#defineOK1
　#defineERROR0
　#defineMAX1000
　typedefstructArcell
　{
　doubleadj;
　}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
　typedefstruct
　{
　charvexs[MAX_VERTEX_NUM];//節點數組
　AdjMatrixarcs;//鄰接矩陣
　intvexnum,arcnum;//圖的當前節點數和弧數
　}MGraph;
　typedefstructPnode//用於普利姆算法
　{
　charadjvex;//節點
　doublelowcost;//權值
　}Pnode,Closedge[MAX_VERTEX_NUM];//記錄頂點集U到V-U的代價最小的邊的輔助數組定義
　typedefstructKnode//用於克魯斯卡爾算法中存儲一條邊及其對應的2個節點
　{
　charch1;//節點1
　charch2;//節點2
　doublevalue;//權值
　}Knode,Dgevalue[MAX_VERTEX_NUM];
　
　
//-------------------------------------------------------------------------------
　intCreateUDG(MGraph&G,Dgevalue&dgevalue);
　intLocateVex(MGraphG,charch);
　intMinimum(MGraphG,Closedgeclosedge);
　voidMiniSpanTree_PRIM(MGraphG,charu);
　voidSortdge(Dgevalue&dgevalue,MGraphG);
　
　
//-------------------------------------------------------------------------------
　intCreateUDG(MGraph&G,Dgevalue&dgevalue)//構造無向加權圖的鄰接矩陣
　{
　inti,j,k;
　cout<<"請輸入圖中節點個數和邊/弧的條數：";
　cin>>G.vexnum>>G.arcnum;
　cout<<"請輸入節點：";
　for(i=0;i<G.vexnum;++i)
　cin>>G.vexs[i];
　for(i=0;i<G.vexnum;++i)//初始化數組
　{
　for(j=0;j<G.vexnum;++j)
　{
　G.arcs[i][j].adj=MAX;
　}
　}
　cout<<"請輸入一條邊依附的定點及邊的權值："<<endl;
　for(k=0;k<G.arcnum;++k)
　{
　cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;
　i=LocateVex(G,dgevalue[k].ch1）;
　j=LocateVex(G,dgevalue[k].ch2）;
　G.arcs[i][j].adj=dgevalue[k].value;
　G.arcs[j][i].adj=G.arcs[i][j].adj;
　}
　returnOK;
　}
　intLocateVex(MGraphG,charch)//確定節點ch在圖G.vexs中的位置
　{
　inta;
　for(inti=0;i<G.vexnum;i++)
　{
　if(G.vexs[i]==ch)
　a=i;
　}
　returna;
　}
　voidMiniSpanTree_PRIM(MGraphG,charu)//普利姆算法求最小生成樹
　{
　inti,j,k;
　Closedgeclosedge;
　k=LocateVex(G,u);
　for(j=0;j<G.vexnum;j++)
　{
　if(j!=k)
　{
　closedge[j].adjvex=u;
　closedge[j].lowcost=G.arcs[k][j].adj;
　}
　}
　closedge[k].lowcost=0;
　for(i=1;i<G.vexnum;i++)
　{
　k=Minimum(G,closedge);
　cout<<"("<<closedge[k].adjvex<<","<<G.vexs[k]<<","<<closedge[k].lowcost<<")"<<endl;
　closedge[k].lowcost=0;
　for(j=0;j<G.vexnum;++j)
　{
　if(G.arcs[k][j].adj<closedge[j].lowcost)
　{
　closedge[j].adjvex=G.vexs[k];
　closedge[j].lowcost=G.arcs[k][j].adj;
　}
　}
　}
　}
　intMinimum(MGraphG,Closedgeclosedge)//求closedge中權值最小的邊，並返回其頂點在vexs中的位置
　{
　inti,j;
　doublek=1000;
　for(i=0;i<G.vexnum;i++)
　{
　if(closedge[i].lowcost!=0&&closedge[i].lowcost<k)
　{
　k=closedge[i].lowcost;
　j=i;
　}
　}
　returnj;
　}
　voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)//克魯斯卡爾算法求最小生成樹
　{
　intp1,p2,i,j;
　intbj[MAX_VERTEX_NUM];//標記數組
　for(i=0;i<G.vexnum;i++)//標記數組初始化
　bj[i]=i;
　Sortdge(dgevalue,G);//將所有權值按從小到大排序
　for(i=0;i<G.arcnum;i++)
　{
　p1=bj[LocateVex(G,dgevalue[i].ch1）];
　p2=bj[LocateVex(G,dgevalue[i].ch2）];
　if(p1!=p2）
　{
　cout<<"("<<dgevalue[i].ch1<<","<<dgevalue[i].ch2<<","<<dgevalue[i].value<<")"<<endl;
　for(j=0;j<G.vexnum;j++)
　{
　if(bj[j]==p2）
　bj[j]=p1;
　}
　}
　}
　}
　voidSortdge(Dgevalue&dgevalue,MGraphG)//對dgevalue中各元素按權值按從小到大排序
　{
　inti,j;
　doubletemp;
　charch1,ch2;
　for(i=0;i<G.arcnum;i++)
　{
　for(j=i;j<G.arcnum;j++)
　{
　if(dgevalue[i].value>dgevalue[j].value)
　{
　temp=dgevalue[i].value;
　dgevalue[i].value=dgevalue[j].value;
　dgevalue[j].value=temp;
　ch1=dgevalue[i].ch1;
　dgevalue[i].ch1=dgevalue[j].ch1;
　dgevalue[j].ch1=ch1;
　ch2=dgevalue[i].ch2;
　dgevalue[i].ch2=dgevalue[j].ch2;
　dgevalue[j].ch2=ch2;
　}
　}
　}
　}
　intmain()
　{
　inti,j;
　MGraphG;
　charu;
　Dgevaluedgevalue;
　CreateUDG(G,dgevalue);
　cout<<"圖的鄰接矩陣為："<<endl;
　for(i=0;i<G.vexnum;i++)
　{
　for(j=0;j<G.vexnum;j++)
　cout<<G.arcs[i][j].adj<<"";
　cout<<endl;
　}
　cout<<"=============普利姆算法===============\n";
　cout<<"請輸入起始點：";
　cin>>u;
　cout<<"構成最小代價生成樹的邊集為：\n";
　MiniSpanTree_PRIM(G,u);
　cout<<"============克魯斯科爾算法=============\n";
　cout<<"構成最小代價生成樹的邊集為：\n";
　MiniSpanTree_KRSL(G,dgevalue);
return0；
　}

Kruskal算法 - pascal語言

program didi;

var

a:array[0..100000] of record

s,t,len:longint;

end;

fa,r:array[0..10000] of longint;

n,i,j,x,y,z:longint;

tot,ans:longint;

count,xx:longint;

procedure quick(l,r:longint);

var

i,j,x,y,t:longint;

begin

i:=l; j:=r;

x:=a[(l+r) div 2].len;

repeat

while x>a[i].len do inc(i);

while x<a[j].len do dec(j);

if i<=j then

begin

y:=a[i]; a[i]:=a[j]; a[j]:=y;

inc(i);dec(j);

end;

until i>j;

if i<r then quick(i,r);

if l<j then quick(l,j);

end;

function find(x:longint):longint;

begin

if fa[x]=x then exit(x);

fa[x]:=find(fa[x]);{路徑壓縮}

exit(fa[x]);

end;

procedure union(x,y:longint);{啓發式合併}

var

t:longint;

begin

x:=find(x);

y:=find(y);

if r[x]>r[y] then

begin

t:=x; x:=y; y:=t;

end;

if r[x]=r[y] then inc(r[x]);

fa[x]:=y;

end;

begin

readln(xx,n);

for i:=1 to xx do fa[i]:=i;

for i:=1 to n do

begin

read(x,y,z);

inc(tot);

a[tot].s:=x;

a[tot].t:=y;

a[tot].len:=z;

end;

quick（1,tot);{將邊排序}

ans:=0;

count:=0;

i:=0;

while count<=x-1 do{count記錄加邊的總數}

begin

inc(i);

with a[i] do

if find(s)<>find(t) then

begin

union(s,t);

ans:=ans+len;

inc(count);

end;

write(ans);

end.

Prim算法 - pascal語言

var

m,n:set of 1..100;

s,t,min,x,y,i,j,k,l,sum,p,ii:longint;

a:array[1..100,1..100]of longint;

begin

readln(p);

for ii:=1 to p do

begin

k:=0; sum:=0;

fillchar(a,sizeof(a),255);

readln(x);

m:=[1];

n:=[2..x];

for i:=1 to x do

begin

for j:=1 to x do

begin

read(a[i,j]);

if a[i,j]=0

then a[i,j]:=maxlongint;

end;

readln;

end;

for l:=1 to x-1 do

begin

min:=maxlongint;

for i:=1 to x do

if i in m

then begin

for j:=1 to x do

begin

if (a[i,j]<min)and(j in n)

then begin

min:=a[i,j];

s:=i;

t:=j;

end;

sum:=sum+min;

m:=m+[t];

n:=n-[t];

inc(k);

end;

writeln(sum);

end;

end.

C++模板

//maxe保存了最大邊數
structedge
{
intu,v,w;

booloperator<(constedge&b)const
{
returnthis->w>b.w;
}
}e[maxe];

//並查集相關
intf[maxn];

inlinevoidinit()
{
for(inti=0;i<maxn;i++)f[i]=i;
}

intfind(intx)
{
if(f[x]==x)returnx;
elsereturnf[x]=find(f[x]);
}

//主算法
intkruskal(intn,intm)
{
//n:點數,m:邊數
//所有邊已經預先儲存在e數組裏
sort(e,e+m);
init();

intans=0;
for(inti=0;i<m;i++)
{
intu=e[i].u,v=e[i].v,w=e[i].w;
if(find(u)==find(v))continue;
f[find(u)]=find(v);
ans+=w;
}

returnans;
}

參考資料

1. 嚴蔚敏．《數據結構與算法分析》：清華大學出版社，2011

最小生成樹的概述圖（1張）

詞條統計

瀏覽次數：次
編輯次數：67次歷史版本
最近更新：四海皆海OL （2024-04-03）

1 概述
2 應用
3 性質
4 算法描述

最小生成樹

目錄

最小生成樹概述

最小生成樹應用

最小生成樹性質

最小生成樹算法描述