數(shù)據(jù)結(jié)構(gòu)課件第三講

第三講生成樹生成樹定義：所有頂點均由邊連接在一起，但不存在回路的圖叫～深度優(yōu)先生成樹與廣度優(yōu)先生成樹生成森林：非連通圖每個連通分量的生成樹一起組成非連通圖的～說明一個圖可以有許多棵不同的生成樹所有生成樹具有以下共同特點：生成樹的頂點個數(shù)與圖的頂點個數(shù)相同生成樹是圖的極小連通子圖一個有n個頂點的連通圖的生成樹有n-1條邊生成樹中任意兩個頂點間的路徑是唯一的在生成樹中再加一條邊必然形成回路含n個頂點n-1條邊的圖不一定是生成樹GHKIV1V2V4V5V3V7V6V8例深度遍歷：V1V2V4V8V5V3V6V7V1V2V4V5V3V7V6V8深度優(yōu)先生成樹V1V2V4V5V3V7V6V8廣度優(yōu)先生成樹V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8廣度遍歷：V1V2V3V4V5V6V7V8例ABLMCFDEGHKIJABLMCFJDEGHKI深度優(yōu)先生成森林最小生成樹問題提出要在n個城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點——表示城市權(quán)——城市間建立通信線路所需花費(fèi)代價希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價）最小———最小代價生成樹問題分析1654327131791812752410n個城市間，最多可設(shè)置n(n-1)/2條線路n個城市間建立通信網(wǎng)，只需n-1條線路問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把所有城市（頂點）均連起來，且總耗費(fèi)（各邊權(quán)值之和）最小構(gòu)造最小生成樹方法方法一：普里姆(Prim)算法算法思想：設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹中邊的集合初始令U={u0},(u0V),TE=在所有uU,vV-U的邊(u,v)E中，找一條代價最小的邊(u0,v0)將(u0,v0)并入集合TE，同時v0并入U重復(fù)上述操作直至U=V為止，則T=(V,{TE})為N的最小生成樹Ch6_3.cV3V1V4V6V5V23652165546如何求連通圖的最小生成樹?？

求解:

連通6個城市且代價最小的交通線路?V3V1V4V6V5V23652165546V3V1V4V6V5V212V3V1V4V6V5V214V3V1V4V6V5V2142V3V1V4V6V5V21452V3V1V4V6V5V21453U={V1}U={V1,V3}U={V1,V3,V6}U={V1,V3,V6,V4}U={V1,V3,V6,V4,V2}U={V1,V3,V6,V4,V2,V5}

有關(guān)數(shù)據(jù)的存儲結(jié)構(gòu)

無向連通網(wǎng)絡(luò):

G

為選擇權(quán)值最小的邊:

置一個一維數(shù)組：closedge[]，以記錄從U到

V-U具有最小代價的邊。對每一頂點vi

V-U,在輔助數(shù)組中相應(yīng)分量closedge[i-1],包括兩域Closedge[i-1].lowcost=Min{cost(u,vi)|u∈U}存儲該邊上的權(quán)Closedge[i-1].adjvex域：存儲該邊依附的在U中的頂點。

普魯姆算法涉及的數(shù)據(jù)和操作：

數(shù)據(jù)：無向連通網(wǎng)絡(luò)

操作:

選擇權(quán)值最小的邊，不妨設(shè)為（u,v)

(u,v)加入TE，u加入UUV-U

viV2V0V3V5V4V-U

vivjV3V1V4V6V5V23652165546例000000

06

1

5maxmax

viadjvexlowcost

012345

viadjvexlowcost

012345020022

05056

4U={v1}U={v1,v3}V3V1V4V6V5V23652165546UU對每一頂點vi

V-U,在輔助數(shù)組中相應(yīng)分量closedge[i-1],包括兩域Closedge[i-1].lowcost=Min{cost(u,vi)|u∈U}存儲該邊上的權(quán)Closedge[i-1].adjvex域：存儲該邊依附的在U中的頂點。V-U={v2,V3,V4,V5,V6}V-U={v2,V4,V5,V6}

0v1v1v100

06

1

5maxmax

lowcost{v1}

0v30v1v3v3

05056

4

adjvexlowcost{v1,v3}

0v30v6v32

050

2

60

adjvexlowcost{v1,v3,v6}

0v305v32

0

5

0060

adjvexlowcost{v1,v3,v6,v4}

0205v22

0000

3

0adjvexlowcost{v1,v3,v6,v4,v2}

020512

000000

adjvexlowcost{v1,v3,v6,v4,v2,v5}iadjvex

012345UV3V1V4V6V5V23652165546closedgev1v2v3v4v5v6用普里姆算法viudPRIM(MGraphG,VertexTypeu){k=LocateVex(G,u);for(j=0;j<G.vexnum;++j)if(j!=k)closedge[j]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;for(i=1;i<G.vexnum;++i){k=mininmum(closedge);printf(closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0;for(j=0;j<G.vexnum.++j)if(G.arcs[k][j].adj<closedge[j].lowcostclosedge[j]={G.vexs[k],G.arcs[k][j].adj}}}方法二：克魯斯卡爾(Kruskal)算法算法思想：設(shè)連通網(wǎng)N=(V,{E})，令最小生成樹初始狀態(tài)為只