數(shù)據(jù)結(jié)構(gòu)課件圖最小生成樹2009級

§7.4最小的生成樹§7.4最小的生成樹生成樹包含無向連通圖G所有頂點的的極小連通子圖最小生成樹：權(quán)（之和）最小的生成樹。32154V6V5V4V3V26V5V4V3V2V1應(yīng)用假設(shè)要在n個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，已知連通n個城市各條線路的費用，如何在最節(jié)省經(jīng)費的前提下建立這個通訊網(wǎng)？網(wǎng)絡(luò)中的SpaningTreeProtocol典型算法：普魯姆(Prim)算法克魯斯卡爾算法3652165546V6V5V4V3V2V1普魯姆(Prim)算法原始數(shù)據(jù)：無向連通網(wǎng)結(jié)果數(shù)據(jù)：最小生成樹32154V6V5V4V3V26V5V4V3V2V1普魯姆(Prim)算法把圖G=(V,E)中所有頂點分成兩組第1組U:包括已在最小生成樹中的頂點;初始時，設(shè)U={v1};第2組V-U：包括尚未加入最小生成樹的頂點;從第2組中選擇與第1組距離最小(邊權(quán)值最小)的頂點，加入第1組（最小生成樹），直至把圖的所有頂點都加到進第1組中。UV-Uv1v3v2v4v5v6UV-U6V5V4V3V2V1

普魯姆算法基本步驟設(shè)U、MST分別為已在生成樹中的頂點集合和邊集合。1）初始時，設(shè)U={u0}，MST=；2）在所有uU

、vV-U的邊中選擇一條權(quán)值最小的邊，不妨設(shè)為（u,v)；3）將v加入U；(u,v)加入MST，4）重復(fù)2)、3)，直到U=V為止；3652165546V6V5V4V3V26V5V4V3V2V1UV-Uv1v3v2v4v5v63652165546V6V5V4V3V26V5V4V3V26V5V4V3V26V5V4V3V26V5V4V3V26V5V4V3V26V5V4V3V26V5V4V3V26V5V4V3V2V1普魯姆(Prim)算法原始數(shù)據(jù)：無向連通網(wǎng)結(jié)果數(shù)據(jù)：最小生成樹32154V6V5V4V3V26V5V4V3V2V1M

=

0615INFINF605INF3INF1505645INF50INF2INF36INF06INFINF42602）在所有uU

、vV-U的邊中選擇一條權(quán)值最小的邊，不妨設(shè)為(u,v)；V1V2V3V4V5V6V1V2V3V4V5V6a)頂點vi(V-U)到頂點集U權(quán)最小邊;b)在上述最小邊中求最小;

0615INFINF605INF3INF15056

4

5INF50INF2INF36INF06INFINF4260UV-Uv1v3v2v4v5v6距離數(shù)組Dist[vi]:頂點vi到頂點集U權(quán)最小邊的權(quán)值(頂點vi到頂點集U的距離)權(quán)最小邊數(shù)組MST[vi]:頂點vi到頂點集U權(quán)最小邊3652165546V6V5V4V3V2V1UV-Uv1v3v2v4v5v605

1

5

64Dist

(v3,v2)

(v1,v3)

(v1,v4)(v3,v5)(v3,v6)MST

0(v1)

1(v2)

2(v3)

3(v4)

4(v5)5(v6)3652165546V6V5V4V3V2V106

1

5

INFINITY

INFINITY

Dist

(v1,v2)

(v1,v3)

(v1,v4)

MST

0(v1)

1(v2)

2(v3)

3(v4)

4(v5)5(v6)3652165546V6V5V4V3V26V5V4V3V2V105

1

5

64Dist

(v3,v2)

(v1,v3)

(v1,v4)

(v3,v5)(v3,v6)

MST

0(v1)

1(v2)

2(v3)

3(v4)

4(v5)5(v6)3652165546V6V5V4V3V26V5V4V3V2V105

1

2

64Dist

(v3,v2)

(v1,v3)

(v6,v4)

(v3,v5)(v3,v6)

MST

0(v1)

1(v2)

2(v3)

3(v4)

4(v5)5(v6)3652165546V6V5V4V3V26V5V4V3V2V105

1

2

64Dist

(v3,v2)

(v1,v3)

(v6,v4)

(v3,v5)(v3,v6)

MST

0(v1)

1(v2)

2(v3)

3(v4)

4(v5)5(v6)3652165546V6V5V4V3V26V5V4V3V2V10

5

1

2

34Dist

(v3,v2)

(v1,v3)

(v6,v4)

(v2,v5)(v3,v6)

MST

0(v1)

1(v2)

2(v3)

3(v4)

4(v5)5(v6)3652165546V6V5V4V3V2V10

5

1

2

3

4Dist

(v3,v2)

(v1,v3)

(v6,v4)

(v2,v5)

(v3,v6)

MST

0(v1)

1(v2)

2(v3)

3(v4)

4(v5)

5(v6)

2(v3)0(v1)5(v6)1(v2)2(v3)MST標識數(shù)組

Mark[vi]:標識頂點是否已在U中距離數(shù)組Dist[vi]

頂點vi到頂點集U權(quán)最小邊的權(quán)值(vi到U的距離)權(quán)最小邊數(shù)組MST[vi]

頂點vi到頂點集U權(quán)最小邊的另一頂點(

U)0(v1)

1(v2)2(v3)3(v4)4(v5)5(v6)-12(v3)0(v1)5(v6)1(v2)2(v3)

MST

051234Dist32154V6V5V4V3V2V1③②①111111MarkvoidMST_Prime(MGraphG,intu0,intDist[],intMST[],intMark[]){//以u0為起點求最小生成樹

for(i=0;i<G.vexnum;++i)//初始化

{Mark[i]=0;Dist[i]=G.arcs[u0][i];if(Dist[i]<INFINITY)MST[i]=u0;elseMST=-1;}//forMark[u0]=1;//u0加入Ufor(i=1;i<G.vexnum;++i){k=SelectMin(Dist,Mark);//在Dist中選擇最小者

Mark[k]=1;//k加入Ufor(j=0;j<G.vexnum;++j)

//修改V-U中頂點到頂點集U的最短距離

if(!Mark[j]&&G.arcs[k][j]<Dist[j]){Dist[j]=G.arcs[k][j];MST[j]=k;}}//for}//MST_Prime3652165546V6V5V4V3V2V1普里姆算法的性能設(shè)n是圖的頂點數(shù),普魯姆算法的時間復(fù)雜度為O(n2)。與邊數(shù)無關(guān)，適用于求邊稠密的網(wǎng)的最小生成樹。

克魯斯卡爾（Kruskual)算法V3V1V4V6V5V236521655461)初始時最小生成樹只包含圖的n個頂點，每個頂點為一棵子樹；2)選取權(quán)值較小且所關(guān)聯(lián)的兩個頂點不在同一子樹的邊，將此邊加入到最小生成樹中；3)重復(fù)2）n-1次，即得到包含n個頂點和n-1條邊的最小生成樹。

克魯斯卡爾（Kruskual)算法的基本步驟V3V1V4V6V5V2V3V1V4V6V5V23652165546V3V1V4V6V5V21V3V1V4V6V5V212V3V1V4V6V5V2123V3V1V4V6V5V21234V3V1V4V6V5V212345V3V1V4V6