第四節(jié)圖的生成樹和最小生成樹

一、圖的生成樹

1、生成樹的概念

對(duì)于具有n個(gè)頂點(diǎn)的連通圖，包含了該圖的全部n個(gè)頂點(diǎn)，僅包含

它的n-1條邊的一個(gè)極小連通子圖被稱為生成樹。

一個(gè)圖的生成樹為一個(gè)無(wú)回路的連通圖。也就是說(shuō)，若在圖中任意

添加一條邊，就會(huì)出現(xiàn)回路；若在圖中去掉任何一條邊，都會(huì)使之成

為非連通圖。

一個(gè)連通圖的生成樹不一定是唯一的。

【例】下圖中圖（b）和（c）是圖（a）的生成樹。

由深度優(yōu)先搜索所得的生成樹稱為深度優(yōu)先生成樹，簡(jiǎn)稱為DFS生

成樹；而由廣度優(yōu)先搜索所得的生成樹稱之為廣度優(yōu)先生成樹，簡(jiǎn)稱

為BFS生成樹。

【例】下圖中圖（b）是圖（a）從V0開始的深度優(yōu)先搜索所得的

生成樹，圖（c）是圖（a）從V0開始的廣度優(yōu)先搜索的生成樹。

從V。開始的深度優(yōu)先搜索序列：Vo,V1,V2,V5,V4,V6,V3,

V7,V8o

從Vo開始的廣度優(yōu)先搜索序列：Vo,V1zV3,V4,V2,V6,V8,

二、最小生成樹

1、最小生成樹的概念

對(duì)于連通的帶權(quán)圖（網(wǎng)）G,其生成樹也是帶權(quán)的。把生成樹各邊的權(quán)

值總和稱為該樹的權(quán)，把權(quán)值最小的生成樹稱為圖的最小生成樹

(MininumSpanningTree,MST)O

【例】圖（b）、（c）、（d）是圖（a）的三棵生成樹。

(b)

2、普里姆（Prim）算法

（1）算法思想

用自然語(yǔ)言描述的Prim算法：設(shè)G=(V,GE)為具有n個(gè)頂點(diǎn)

的帶權(quán)連通圖，T=(U,TE)為G的一個(gè)子圖，初始時(shí)，有丁￡二空，

算法描述為：從中選擇一個(gè)頂點(diǎn)僅在

U={Vi},ViGVoPrimGV

中，而另一個(gè)頂點(diǎn)在U中，并且權(quán)值最小的邊加入集合TE中，同時(shí)

將該邊僅在V中的那個(gè)頂點(diǎn)加入集合U中。重復(fù)上述過(guò)程n-1次，直

到U=V,止匕時(shí)T為G的最小生成樹。

【例】試用Prim算法構(gòu)造(a)圖的最小生成樹，要求分步給出

構(gòu)造過(guò)程

【分析】算法一開始取u={l},然后到V-U中找一條代價(jià)最小且依

附于頂點(diǎn)1的邊，(u。,vo)=(l,3),將vo=3加入集合U中，修改

輔助數(shù)組中的值。使minedge[3].lowcost=0,以表示頂點(diǎn)3已并入

U,由于邊(3,6)上的權(quán)值是一條最小且依附于頂點(diǎn)集U中頂點(diǎn)的

邊，因此修改minedge⑹的值，依此類推，直到U=V,其過(guò)程如表

所示。

23456Uv-u說(shuō)明

ver①①①

{1}[2,3,4,5,6)u(l,3)邊最短

lowcost605

ver③①③③

0{1，3}{2,4,5,6}u(3,6)邊最短

lowcost5560

Ver③⑥③

00{1,3,6}[2,4,5)u(6,4)也最短

lowcost5目6

ver③③

000{1.3,6,4}{215}u(3,2)邊最短

lowcost同6

ver②

0000{1,3,6,4,2}{5}U(2.5)邊最短

lowcost

ver

00000{1,3,6,4,2,5}力

lowcost

(2)算法描述

附設(shè)一個(gè)輔助數(shù)組minedge[vtxptr],記錄從U到V-U具有最小

代價(jià)的邊。對(duì)每個(gè)頂點(diǎn)vwV-U,在輔助數(shù)組中存在一個(gè)分量

minedge[v],它包括兩個(gè)域，其中l(wèi)owcost存儲(chǔ)該邊上的權(quán)值，ver

域存儲(chǔ)該邊的依附在U中的頂點(diǎn)。Minedge[v]=min{cost(u,v),u

GU},(cost(u,v)表示該邊的權(quán))。

【算法描述】

typedefintVRType;

typedefstruct

{ertexTypeVer;

VRTypelowcost;

}minedge[MaxVertexNum];〃從頂點(diǎn)集u至!]V-U

的代價(jià)最小的邊的輔助數(shù)組

voidPrim(MGraphG,VertexTypeu,intn)

{〃采用鄰接矩陣存儲(chǔ)結(jié)構(gòu)表示圖

intk,v,j;

k=vtxNum(G,u);/儆頂點(diǎn)u在輔

助數(shù)組中的下標(biāo)

for(v=o;v<n;v++)〃輔助數(shù)組初始化

if(v!=k)

{minedge[v].ver=u;

minedge[v].lowcost=G.arcs[k][v];

)

minedge[k].lowcost=0,〃初始,U={u}

forQ=l;j<n;j++)〃選擇其余的n-1

個(gè)頂點(diǎn)

{k=min(minedge(j])；

//l<j<n-l，找一個(gè)滿

足條件的最小邊(u,k),ueu,keV-u

printf(minedge[k].ver,G.vexs[k]);

〃輸出生成樹的邊

minedge[k].lowcost=0;〃第k個(gè)頂點(diǎn)并

入u

for(v=0;v<n;v++)

if(G.arcs[k][v]<minedge[v].lowcost)

〃重新選擇最小邊

{minedge[v].ver=G.vexs[k];

mindege[v].lowcost=G.arcs[k][v];

)

)

)

普里姆算法的時(shí)間復(fù)雜度是0(n2)

【例】試用Prim算法構(gòu)造下圖的最小生成樹，畫出所有可能的情

況。

圖附1-15

隱藏答案

【解析】根據(jù)Prim算法構(gòu)造，本題的最小生成樹有的圖有兩種。

【答案】最小生成樹有的圖有兩種，如圖所示

3、克魯斯卡爾(Krtskal)算法

(1)算法思想

假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是

G的最小生成樹，U的初值等于V,即包含有G中的全部頂點(diǎn)。T的

初始狀態(tài)是只含有n個(gè)頂點(diǎn)而無(wú)邊的森林T=(V,(p)o

該算法的基本思想是：將圖G中的邊按權(quán)值從小到大的順序依次選

取E中的邊(u,v),若選取的邊使生成樹T不形成回路，則把它并入

TE中，保留作為T的一條邊;若選取的邊使生成樹T形成回路，則將

其舍棄，如此進(jìn)行下去直到TE中包含n-1條邊為止，此時(shí)的T即為

最小生成樹。

【例】試用克魯斯卡爾(Krtskal)算法構(gòu)造(a)圖的最小生成

當(dāng)前講授

(2)算法描述

Kruskal(G)

(〃求連通網(wǎng)G的一棵MST

T=(v,ip);〃初始化T為只含有n個(gè)頂

點(diǎn)而無(wú)邊的森林

按權(quán)值升序?qū)吋疎中的邊進(jìn)行排序，結(jié)果存入E[O...e-l]中

for(i=0;i<e;i++)//e為圖G