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

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

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

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

=

0615INFINF605INF3INF1505645INF50INF2INF36INF06INFINF42602）在所有uU

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

0615INFINF605INF3INF15056

4

5INF50INF2INF36INF06INFINF4260UV-Uv1v3v2v4v5v6距離數(shù)組Dist[vi]:頂點(diǎn)vi到頂點(diǎn)集U權(quán)最小邊的權(quán)值(頂點(diǎn)vi到頂點(diǎn)集U的距離)權(quán)最小邊數(shù)組MST[vi]:頂點(diǎn)vi到頂點(diǎn)集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標(biāo)識(shí)數(shù)組

Mark[vi]:標(biāo)識(shí)頂點(diǎn)是否已在U中距離數(shù)組Dist[vi]

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

頂點(diǎn)vi到頂點(diǎn)集U權(quán)最小邊的另一頂點(diǎ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[]){//以u(píng)0為起點(diǎn)求最小生成樹(shù)

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加入U(xiǎn)for(i=1;i<G.vexnum;++i){k=SelectMin(Dist,Mark);//在Dist中選擇最小者

Mark[k]=1;//k加入U(xiǎn)for(j=0;j<G.vexnum;++j)

//修改V-U中頂點(diǎn)到頂點(diǎn)集U的最短距離

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

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

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