數(shù)據(jù)結(jié)構(gòu) 圖3-最小生成樹

1、數(shù)據(jù)結(jié)構(gòu)講義 - 最小生成樹l若圖是連通的或強(qiáng)連通的，則從圖中某一個頂點(diǎn)出發(fā)可以訪問到圖中所有頂點(diǎn)；l若圖是非連通的或非強(qiáng)連通圖，則需從圖中多個頂點(diǎn)出發(fā)搜索訪問而每一次從一個新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪問序列恰為每個連通分量中的頂點(diǎn)集。DEABCFJLMGHIKDEGHIKABCFJLM 對于連通圖，深度優(yōu)先搜索遍歷算法及廣度優(yōu)先搜索遍歷算法中遍歷圖過程中歷經(jīng)邊的集合和頂點(diǎn)集合一起構(gòu)成連通圖的極小連通子圖。它是連通圖的一顆生成樹。生成樹：生成樹：是一個極小連通子圖，它含有圖是一個極小連通子圖，它含有圖中全部頂點(diǎn)，但只有中全部頂點(diǎn)，但只有n-1n-1條邊。條邊。 由深度優(yōu)先搜索遍歷得

2、到的生成樹，稱為深度優(yōu)先生成樹，由廣度優(yōu)先搜索遍歷得到的生成樹，稱為廣度優(yōu)先生成樹。見下頁無向圖G7的兩種生成樹。 1 4 2 5 3 6 8 7 2 7 6 8 3 5 4 1 (a) 深度優(yōu)先生成樹 (b) 廣度優(yōu)先生成樹 兩種生成樹示意圖 3 1 2 4 5 7 6 8 無向圖 G7 DFS生生成成樹樹v0v1v2v4v4v3鄰接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生生成成樹樹v0v1v3v2v4無向連通圖無向連通圖2生成森林 若一個圖是非連通圖或非強(qiáng)連通圖，但有若干個連通分量或若干個強(qiáng)連通分量，則通過深度優(yōu)先搜索遍歷或廣度優(yōu)先搜索遍歷，

3、不可以得到生成樹，但可以得到生成森林，且若非連通圖有 n 個頂點(diǎn)，m 個連通分量或強(qiáng)連通分量，則可以遍歷得到m棵生成樹，合起來為生成森林，森林中包含n-m條樹邊。生成森林可以利用非連通圖的深度優(yōu)先搜索遍歷或非連通圖的廣度優(yōu)先搜索遍歷算法得到。DEABCFJLMGHIK求解步驟：求解步驟：Step1:Step1:先求出鄰接矩陣或鄰接表；先求出鄰接矩陣或鄰接表；Step2:Step2:寫出寫出DFSDFS或或BFSBFS結(jié)果序列；結(jié)果序列；Step3:Step3:畫出對應(yīng)子圖或生成森林。畫出對應(yīng)子圖或生成森林。這是一個無向非連通圖這是一個無向非連通圖下面選用鄰接表方式來求深度優(yōu)先搜索生成森林下面選

4、用鄰接表方式來求深度優(yōu)先搜索生成森林注：亦可由鄰接矩陣或鄰接表直接畫出生成森林注：亦可由鄰接矩陣或鄰接表直接畫出生成森林115 5M12L11K10J9I8H7G6F5E4D3C2B1A01201200437810661011126709121911112294710811DEGHIK子圖子圖1：再寫出再寫出DFS結(jié)果（結(jié)果（3次）次）ABMJLCFDEGHKIABCFJLM先寫出鄰接表（或鄰接矩陣）：先寫出鄰接表（或鄰接矩陣）：子圖子圖2：子圖子圖3：最小連最小連通！通！DEGHIK子圖子圖(或連通分量或連通分量)ABCFJLMABCFJLMDEGHIK生生成成森森林林首先明確：首先明確：使

5、用不同的遍歷圖的方法，可以得到不同的生成樹；從使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹。不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，按照生成樹的定義，n n 個頂點(diǎn)的個頂點(diǎn)的連通網(wǎng)絡(luò)連通網(wǎng)絡(luò)的生成樹有的生成樹有 n n 個頂點(diǎn)、個頂點(diǎn)、n-n-1 1 條邊。條邊。即有權(quán)圖即有權(quán)圖目標(biāo)：目標(biāo)：在網(wǎng)絡(luò)的多個生成樹中，尋找一個在網(wǎng)絡(luò)的多個生成樹中，尋找一個各邊權(quán)值之和最小各邊權(quán)值之和最小的的生成樹。生成樹。構(gòu)造最小生成樹的準(zhǔn)則構(gòu)造最小生成樹的準(zhǔn)則v 必須只使用該網(wǎng)絡(luò)中的必須只使用該網(wǎng)絡(luò)中的邊邊來構(gòu)造最小生成樹；來構(gòu)造最小生成樹；v 必須使用

6、且僅使用必須使用且僅使用n n-1-1條邊條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的來聯(lián)結(jié)網(wǎng)絡(luò)中的n n個頂點(diǎn)；個頂點(diǎn)；v 不能使用產(chǎn)生回路的邊。不能使用產(chǎn)生回路的邊。欲在欲在n n個城市間建立通信網(wǎng)，則個城市間建立通信網(wǎng)，則n n個城市應(yīng)鋪個城市應(yīng)鋪n-1n-1條線路；條線路；但因為每條線路都會有對應(yīng)的經(jīng)濟(jì)成本，而但因為每條線路都會有對應(yīng)的經(jīng)濟(jì)成本，而n n個城市可能有個城市可能有n(n-n(n-1)/2 1)/2 條線路，那么，條線路，那么，如何如何只能只能選擇選擇n n1 1條線路，使總費(fèi)用最少？條線路，使總費(fèi)用最少？數(shù)學(xué)模型：數(shù)學(xué)模型：頂點(diǎn)頂點(diǎn)表示城市，有表示城市，有n n個；個；邊邊表示線路，有表示線路，有

7、n n1 1條；條；邊的權(quán)值邊的權(quán)值表示線路的經(jīng)濟(jì)代價；表示線路的經(jīng)濟(jì)代價；連通網(wǎng)連通網(wǎng)表示表示n n個城市間通信網(wǎng)。個城市間通信網(wǎng)。顯然此連通網(wǎng)顯然此連通網(wǎng)是一個生成樹！是一個生成樹！問題抽象：問題抽象： n個頂點(diǎn)的生成樹很多，需要從中選一棵個頂點(diǎn)的生成樹很多，需要從中選一棵代價最代價最小小的生成樹，即該樹的生成樹，即該樹各邊的代價之和各邊的代價之和最小。此樹便稱為最小最小。此樹便稱為最小生成樹生成樹MST(Minimum cost Spanning Tree)16543271317918127524101564325791013下面僅討論無向網(wǎng)的最小生成樹問題。普里姆方法的思想是：在圖中任

8、取一個頂點(diǎn)K作為開始點(diǎn)，令U=k，W=V-U，其中V為圖中所有頂點(diǎn)集，然后找一個頂點(diǎn)在U中，另一個頂點(diǎn)在W中的邊中最短的一條，找到后，將該邊作為最小生成樹的樹邊保存起來，并將該邊頂點(diǎn)全部加入U集合中，并從W中刪去這些頂點(diǎn)，然后重新調(diào)整U中頂點(diǎn)到W中頂點(diǎn)的距離, 使之保持最小，再重復(fù)此過程，直到W為空集止。求解過程參見下頁圖。（先深度再廣度） 例1654326513566425131163141643142116432142516543214253Prim算法構(gòu)造最小生成樹演示假設(shè)開始頂點(diǎn)就選為頂點(diǎn)1，故首先有U=1，W=2，3，4，5，6 (a )無向網(wǎng) (b) u=1 w=2,3,4,5,6

9、 6 4 1 2 4 3 6 2 1 3 5 7 6 5 5 5 1 2 3 4 5 6 6 5 1 i123456closesti111111lowcosti 0615 06246053207545705135065160closest用于存放頂點(diǎn)序號用于存放頂點(diǎn)序號lowest存放權(quán)值存放權(quán)值 3 1 2 4 6 5 6 1 4 5 5 5 3 1 2 4 5 6 4 2 1 5 5 (c ) u=1,3 w=2,4,5,6 (d) u=1,3,6 w=2,4,5 i123456closesti131133lowcosti 0505 54 i123456closesti131633lowc

10、osti 0502 50 3 1 2 4 6 5 6 4 2 1 5 5 (e) u=1,3,6,4 w=2,5 (f) u=1,3,6,4,2 w=5 1 2 4 3 5 6 4 2 1 5 3 (g) u=1,3,6,4,2,5 w= 5 4 2 1 3 1 2 4 3 5 6 prim 方法構(gòu)造最小生成樹的過程 i123456closesti131633lowcosti 050050i123456closesti131623lowcosti 000030 i123456closesti131623lowcosti 000000 1 克魯斯卡爾算法基本思想克魯斯卡爾算法基本思想克魯斯卡爾算法的基本思想是：將圖中所有邊按權(quán)值遞增順序排列，依次選定取權(quán)值較小的邊，但要求后面選取的邊不能與前面選取的邊構(gòu)成回路，若構(gòu)成回路，則放棄該條邊，再去選后面權(quán)值較大的邊，n個頂點(diǎn)的圖中，選夠n-1條邊即可。 例如，對上圖中無向網(wǎng)，用克魯斯卡爾算法求最小生成樹的過程見下圖。 2 4 5 6 1 3 1 2 5 1 3 1 4 2 6 (a) 選第 1 條邊 (b) 選第 2 條邊 (c ) 選第 3 條邊 (d) 選第 4 條邊 2 3 5 1 3 1 4 6 2 6 4 2 1 2 3 5 1 4 3 6 1 2 4 3