最小生成樹算法及應(yīng)用

1、最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 一、生成樹的概念一、生成樹的概念 若圖是連通的無向圖或強(qiáng)連通的有向圖，則從圖中任意一個(gè)頂點(diǎn)出發(fā)調(diào)用一若圖是連通的無向圖或強(qiáng)連通的有向圖，則從圖中任意一個(gè)頂點(diǎn)出發(fā)調(diào)用一次次bfsbfs或或dfsdfs后，便可以系統(tǒng)地訪問圖中所有頂點(diǎn)；若圖是有根的有向圖，則從根后，便可以系統(tǒng)地訪問圖中所有頂點(diǎn)；若圖是有根的有向圖，則從根出發(fā)通過調(diào)用一次出發(fā)通過調(diào)用一次dfsdfs或或bfsbfs，亦可系統(tǒng)地訪問所有頂點(diǎn)。在這種情況下，圖中所，亦可系統(tǒng)地訪問所有頂點(diǎn)。在這種情況下，圖中所有頂點(diǎn)加上遍歷過程中經(jīng)過的邊所構(gòu)成的子圖，稱為原圖的生成樹。有頂點(diǎn)加上遍歷過程中經(jīng)過的邊

2、所構(gòu)成的子圖，稱為原圖的生成樹。 對(duì)于不連通的無向圖和不是強(qiáng)連通的有向圖，若有根或者從根外的任意頂點(diǎn)對(duì)于不連通的無向圖和不是強(qiáng)連通的有向圖，若有根或者從根外的任意頂點(diǎn)出發(fā)，調(diào)用一次出發(fā)，調(diào)用一次bfsbfs或或dfsdfs后，一般不能系統(tǒng)地訪問所有頂點(diǎn)，而只能得到以出發(fā)后，一般不能系統(tǒng)地訪問所有頂點(diǎn)，而只能得到以出發(fā)點(diǎn)為根的連通分支（或強(qiáng)連通分支）的生成樹。要訪問其它頂點(diǎn)，還需要從沒有點(diǎn)為根的連通分支（或強(qiáng)連通分支）的生成樹。要訪問其它頂點(diǎn)，還需要從沒有訪問過的頂點(diǎn)中找一個(gè)頂點(diǎn)作為起始點(diǎn)，再次調(diào)用訪問過的頂點(diǎn)中找一個(gè)頂點(diǎn)作為起始點(diǎn)，再次調(diào)用bfsbfs或或dfsdfs，這樣得到的是生成，這樣得

3、到的是生成森林。森林。 由此可以看出，由此可以看出，一個(gè)圖的生成樹是不唯一的一個(gè)圖的生成樹是不唯一的，不同的搜索方法可以得到不同，不同的搜索方法可以得到不同的生成樹，即使是同一種搜索方法，出發(fā)點(diǎn)不同亦可導(dǎo)致不同的生成樹。的生成樹，即使是同一種搜索方法，出發(fā)點(diǎn)不同亦可導(dǎo)致不同的生成樹。 可以證明：具有可以證明：具有n n個(gè)頂點(diǎn)的帶權(quán)連通圖，其對(duì)應(yīng)的生成樹有個(gè)頂點(diǎn)的帶權(quán)連通圖，其對(duì)應(yīng)的生成樹有n-1n-1條邊。條邊。 最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 二、二、求圖的最小生成樹算法求圖的最小生成樹算法 嚴(yán)格來說，如果圖嚴(yán)格來說，如果圖G=G=（V V

4、，E E）是一個(gè)連通的無向圖，則把它的全部頂點(diǎn)）是一個(gè)連通的無向圖，則把它的全部頂點(diǎn)V V和和一部分邊一部分邊EE構(gòu)成一個(gè)子圖構(gòu)成一個(gè)子圖GG，即，即G=G=（V V， EE），且邊集），且邊集EE能將圖中所有能將圖中所有頂點(diǎn)連通又不形成回路，則稱子圖頂點(diǎn)連通又不形成回路，則稱子圖GG是圖是圖G G的一棵生成樹。的一棵生成樹。 對(duì)于帶權(quán)連通圖，生成樹的權(quán)即為生成樹中所有邊上的權(quán)值總和，權(quán)值最對(duì)于帶權(quán)連通圖，生成樹的權(quán)即為生成樹中所有邊上的權(quán)值總和，權(quán)值最小的生成樹，稱為圖的最小生成樹。小的生成樹，稱為圖的最小生成樹。 求圖的最小生成樹具有很高的實(shí)際應(yīng)用價(jià)值，比如下面的這個(gè)例題。求圖的最小生成樹

5、具有很高的實(shí)際應(yīng)用價(jià)值，比如下面的這個(gè)例題。 最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 例例1 1、城市公交網(wǎng)、城市公交網(wǎng) 問題描述問題描述 有一張城市地圖，圖中的頂點(diǎn)為城市，無向邊代表兩個(gè)城市間的連通關(guān)系，有一張城市地圖，圖中的頂點(diǎn)為城市，無向邊代表兩個(gè)城市間的連通關(guān)系，邊上的權(quán)為在這兩個(gè)城市之間修建高速公路的造價(jià)，研究后發(fā)現(xiàn)，這個(gè)地圖有一個(gè)邊上的權(quán)為在這兩個(gè)城市之間修建高速公路的造價(jià)，研究后發(fā)現(xiàn)，這個(gè)地圖有一個(gè)特點(diǎn)，即任一對(duì)城市都是連通的。現(xiàn)在的問題是，要修建若干高速公路把所有城市特點(diǎn)，即任一對(duì)城市都是連通的?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設(shè)計(jì)可使得工程的總造價(jià)

6、最少。聯(lián)系起來，問如何設(shè)計(jì)可使得工程的總造價(jià)最少。 輸入輸入 n n（城市數(shù)，（城市數(shù)，1=1=n=100n=100）；）； e e（邊數(shù)）；（邊數(shù)）； 以下以下e e行，每行行，每行3 3個(gè)數(shù)個(gè)數(shù)i,j,wi,j,wijij，表示在城市，表示在城市i,ji,j之間修建高速公路的造價(jià)。之間修建高速公路的造價(jià)。 輸出輸出 n-1 n-1行，每行為兩個(gè)城市的序號(hào)，表明這兩個(gè)城市間建一條高速公路。行，每行為兩個(gè)城市的序號(hào)，表明這兩個(gè)城市間建一條高速公路。 最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 舉例舉例 下面的圖（下面的圖（A A）表示一個(gè)）表示一個(gè)5 5個(gè)城市的地圖，圖（個(gè)城市的地圖，圖（B B

7、）、（）、（C C）是對(duì)圖（）是對(duì)圖（A A）分別進(jìn)）分別進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的一棵生成樹，其權(quán)和分別為行深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的一棵生成樹，其權(quán)和分別為2020和和3333，前者比，前者比后者好一些，但并不是最小生成樹，最小生成樹的權(quán)和為后者好一些，但并不是最小生成樹，最小生成樹的權(quán)和為1919。 問題分析問題分析 出發(fā)點(diǎn)：具有出發(fā)點(diǎn)：具有n n個(gè)頂點(diǎn)的帶權(quán)連通圖，其對(duì)應(yīng)的生成樹有個(gè)頂點(diǎn)的帶權(quán)連通圖，其對(duì)應(yīng)的生成樹有n-1n-1條邊！條邊！ 那么選哪那么選哪n-1n-1條邊呢？條邊呢？ 設(shè)圖設(shè)圖G G的度為的度為n n，G=G=（V V，E E） 我們介紹兩種基于貪心的

8、算法，我們介紹兩種基于貪心的算法，PrimPrim算法和算法和KruskalKruskal算法。算法。 最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 1 1、用、用PrimPrim算法求最小生成樹的思想如下：算法求最小生成樹的思想如下：設(shè)置一個(gè)頂點(diǎn)的集合設(shè)置一個(gè)頂點(diǎn)的集合S S和一個(gè)邊的集合和一個(gè)邊的集合TETE，S S和和TETE的初始狀態(tài)均為空集；的初始狀態(tài)均為空集；選定圖中的一個(gè)頂點(diǎn)選定圖中的一個(gè)頂點(diǎn)K K，從，從K K開始生成最小生成樹，將開始生成最小生成樹，將K K加入到集合加入到集合S S；重復(fù)下列操作，直到選取了重復(fù)下列操作，直到選取了n-1n-1條邊：條邊： 選取一條權(quán)值最小的邊（

9、選取一條權(quán)值最小的邊（X X，Y Y），其中），其中XSXS，not (YS)not (YS)； 將頂點(diǎn)將頂點(diǎn)Y Y加入集合加入集合S S，邊（，邊（X X，Y Y）加入集合）加入集合TETE；得到最小生成樹得到最小生成樹T =T =（S S，TETE） 。 如何證明如何證明PrimPrim算法的正確性呢？提示：用反證法。算法的正確性呢？提示：用反證法。 因?yàn)椴僮魇茄刂呥M(jìn)行的，所以數(shù)據(jù)結(jié)構(gòu)宜采用邊集數(shù)組表示法。因?yàn)椴僮魇茄刂呥M(jìn)行的，所以數(shù)據(jù)結(jié)構(gòu)宜采用邊集數(shù)組表示法。 最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 從文件中讀入圖的鄰接矩陣從文件中讀入圖的鄰接矩陣g g； 邊集數(shù)組邊集數(shù)組elis

10、telist初始化；初始化；For i:=1 To n-1 Do For i:=1 To n-1 Do Begin Begin elisti.fromv:=1 elisti.fromv:=1；elisti.endv:=i+1elisti.endv:=i+1；elistelisti.weight:=g1,i+1i.weight:=g1,i+1； EndEnd； 求出最小生成樹的求出最小生成樹的n-1n-1條邊；條邊； For k:=1 To n-1 DoFor k:=1 To n-1 Do Begin Begin min:=maxint min:=maxint；m:=km:=k； For j:=

11、k To n-1 Do For j:=k To n-1 Do 查找權(quán)值最小的一條邊查找權(quán)值最小的一條邊 If elistj.weightmin Then Begin min:=elistIf elistj.weightmin Then Begin min:=elistj.weightj.weight；m:=jm:=j；EndEnd； If mk Then Begin t:=elistkIf mk Then Begin t:=elistk；elistk:=elistmelistk:=elistm；elistelistm:=tm:=t；EndEnd； 把權(quán)值最小的邊調(diào)到第把權(quán)值最小的邊調(diào)到第k k

12、個(gè)單元個(gè)單元 j:=elistk.endvj:=elistk.endv； jj為新加入的頂點(diǎn)為新加入的頂點(diǎn) For i:=k+1 To n-1 Do For i:=k+1 To n-1 Do 修改未加入的邊集修改未加入的邊集 Begin s:=elisti.endvBegin s:=elisti.endv； w:=gj,sw:=gj,s； If welisti.weight Then Begin elisti.weight:=wIf welisti.weight Then Begin elisti.weight:=w；elisti.fromvelisti.fromv:=j:=j；EndEnd；

13、 EndEnd； EndEnd； 輸出；輸出； PrimPrim算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 2 2、用、用KruskalKruskal算法求最小生成樹的思想如下：算法求最小生成樹的思想如下： 設(shè)最小生成樹為設(shè)最小生成樹為T=T=（V V，TETE），設(shè)置邊的集合），設(shè)置邊的集合TETE的初始狀態(tài)為空集。將圖的初始狀態(tài)為空集。將圖G G中的中的邊按權(quán)值從小到大排好序，然后從小的開始依次選取，若選取的邊使生成樹邊按權(quán)值從小到大排好序，然后從小的開始依次選取，若選取的邊使生成樹T T不形不形成回路，則把它并入成回路，則把它并入TETE中，保留作為中，保留作為T T的

14、一條邊；若選取的邊使生成樹形成回路，的一條邊；若選取的邊使生成樹形成回路，則將其舍棄；如此進(jìn)行下去，直到則將其舍棄；如此進(jìn)行下去，直到TETE中包含中包含n-1n-1條邊為止。最后的條邊為止。最后的T T即為最小生成樹。即為最小生成樹。 如何證明呢？如何證明呢？ 最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 KruskalKruskal算法在實(shí)現(xiàn)過程中的關(guān)鍵和難點(diǎn)在于：如何判斷欲加入的一條邊算法在實(shí)現(xiàn)過程中的關(guān)鍵和難點(diǎn)在于：如何判斷欲加入的一條邊是否與生成樹中已保留的邊形成回路？是否與生成樹中已保留的邊形成回路？ 我們可以將頂點(diǎn)劃分到不同的集合中，每個(gè)集合中的頂點(diǎn)表示一個(gè)無回路我們可以將頂點(diǎn)劃分到

15、不同的集合中，每個(gè)集合中的頂點(diǎn)表示一個(gè)無回路的連通分量，很明顯算法開始時(shí)，把所有的連通分量，很明顯算法開始時(shí)，把所有n n個(gè)頂點(diǎn)劃分到個(gè)頂點(diǎn)劃分到n n個(gè)集合中，每個(gè)集合個(gè)集合中，每個(gè)集合只有一個(gè)頂點(diǎn)，表明頂點(diǎn)之間互不相通。當(dāng)選取一條邊時(shí)，若它的兩個(gè)頂點(diǎn)分只有一個(gè)頂點(diǎn)，表明頂點(diǎn)之間互不相通。當(dāng)選取一條邊時(shí)，若它的兩個(gè)頂點(diǎn)分屬于不同的集合，則表明此邊連通了兩個(gè)不同的連通分量，因每個(gè)連通分量無屬于不同的集合，則表明此邊連通了兩個(gè)不同的連通分量，因每個(gè)連通分量無回路，所以連通后得到的連通分量仍不會(huì)產(chǎn)生回路，因此這條邊應(yīng)該保留，且回路，所以連通后得到的連通分量仍不會(huì)產(chǎn)生回路，因此這條邊應(yīng)該保留，且把它

16、們作為一個(gè)連通分量，即把它的兩個(gè)頂點(diǎn)所在集合合并成一個(gè)集合。如果把它們作為一個(gè)連通分量，即把它的兩個(gè)頂點(diǎn)所在集合合并成一個(gè)集合。如果選取的一條邊的兩個(gè)頂點(diǎn)屬于同一個(gè)集合，則此邊應(yīng)該舍棄，因?yàn)橥粋€(gè)集合選取的一條邊的兩個(gè)頂點(diǎn)屬于同一個(gè)集合，則此邊應(yīng)該舍棄，因?yàn)橥粋€(gè)集合中的頂點(diǎn)是連通無回路的，若再加入一條邊則必然產(chǎn)生回路。中的頂點(diǎn)是連通無回路的，若再加入一條邊則必然產(chǎn)生回路。 就是并查集的思想。就是并查集的思想。最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 將圖的存儲(chǔ)結(jié)構(gòu)轉(zhuǎn)換成邊集數(shù)組表示的形式將圖的存儲(chǔ)結(jié)構(gòu)轉(zhuǎn)換成邊集數(shù)組表示的形式elistelist，并按照權(quán)值從小到大排好序；，并按照權(quán)值從小到大

17、排好序； 設(shè)數(shù)組設(shè)數(shù)組C1.n-1C1.n-1用來存儲(chǔ)最小生成樹的所有邊，用來存儲(chǔ)最小生成樹的所有邊，CiCi是第是第i i次選取的可行邊在排好序的次選取的可行邊在排好序的elistelist中的下標(biāo)；中的下標(biāo)； 設(shè)一個(gè)數(shù)組設(shè)一個(gè)數(shù)組S1.nS1.n，SiSi都是集合，初始時(shí)都是集合，初始時(shí)Si= i Si= i 。 i:=1i:=1； 獲取的第獲取的第i i條最小生成樹的邊條最小生成樹的邊 j:=1 j:=1； 邊集數(shù)組的下標(biāo)邊集數(shù)組的下標(biāo) While i=n-1 Do While i=n-1 Do Begin Begin For k:=1 To n Do Begin For k:=1 To

18、 n Do Begin 取出第取出第j j條邊，記下兩個(gè)頂點(diǎn)分屬的集合序號(hào)條邊，記下兩個(gè)頂點(diǎn)分屬的集合序號(hào) If elistj.fromvIf elistj.fromv in sk Then m1:=k in sk Then m1:=k； If elistj.endvIf elistj.endv in sk Then m2:=k in sk Then m2:=k； EndEnd； If m1m2 Then Begin If m1m2 Then Begin 找到的找到的elistelist第第j j條邊滿足條件，作為第條邊滿足條件，作為第i i條邊保留條邊保留 Ci:=jCi:=j；i:=i+1

19、i:=i+1； sm1:=sm1+sm2sm1:=sm1+sm2； 合并兩個(gè)集合合并兩個(gè)集合 sm2:= sm2:= ； 另一集合置空另一集合置空 EndEnd； j:=j+1j:=j+1； 取下條邊，繼續(xù)判斷取下條邊，繼續(xù)判斷 EndEnd； 輸出最小生成樹的各邊：輸出最小生成樹的各邊：elistelistCiCi KruskalKruskal算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 二、二、求圖的最小生成樹算法小結(jié)求圖的最小生成樹算法小結(jié) 都是基于貪心算法都是基于貪心算法時(shí)間復(fù)雜度均為時(shí)間復(fù)雜度均為O O（n n* *n n） PrimPrim算法和算法和Kruskal

20、Kruskal算法算法三、應(yīng)用舉例三、應(yīng)用舉例例例2 2、最優(yōu)布線問題（、最優(yōu)布線問題（wire.?wire.?） 學(xué)校有學(xué)校有n n臺(tái)計(jì)算機(jī)，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺(tái)計(jì)算機(jī)被連接是指它們時(shí)臺(tái)計(jì)算機(jī)，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺(tái)計(jì)算機(jī)被連接是指它們時(shí)間有數(shù)據(jù)線連接。由于計(jì)算機(jī)所處的位置不同，因此不同的兩臺(tái)計(jì)算機(jī)的連接費(fèi)用往往是不同的。間有數(shù)據(jù)線連接。由于計(jì)算機(jī)所處的位置不同，因此不同的兩臺(tái)計(jì)算機(jī)的連接費(fèi)用往往是不同的。 當(dāng)然，如果將任意兩臺(tái)計(jì)算機(jī)都用數(shù)據(jù)線連接，費(fèi)用將是相當(dāng)龐大的。為了節(jié)省費(fèi)用，我們采用數(shù)據(jù)當(dāng)然，如果將任意兩臺(tái)計(jì)算機(jī)都用數(shù)據(jù)線連接

21、，費(fèi)用將是相當(dāng)龐大的。為了節(jié)省費(fèi)用，我們采用數(shù)據(jù)的間接傳輸手段，即一臺(tái)計(jì)算機(jī)可以間接的通過若干臺(tái)計(jì)算機(jī)（作為中轉(zhuǎn)）來實(shí)現(xiàn)與另一臺(tái)計(jì)算機(jī)的連接。的間接傳輸手段，即一臺(tái)計(jì)算機(jī)可以間接的通過若干臺(tái)計(jì)算機(jī)（作為中轉(zhuǎn)）來實(shí)現(xiàn)與另一臺(tái)計(jì)算機(jī)的連接。 現(xiàn)在由你負(fù)責(zé)連接這些計(jì)算機(jī)，你的任務(wù)是使任意兩臺(tái)計(jì)算機(jī)都連通（不管是直接的或間接的）?，F(xiàn)在由你負(fù)責(zé)連接這些計(jì)算機(jī)，你的任務(wù)是使任意兩臺(tái)計(jì)算機(jī)都連通（不管是直接的或間接的）。 輸入格式輸入格式 輸入文件第一行為整數(shù)輸入文件第一行為整數(shù)n n（2=n=1002=n0 then cp：=1 else cp：=-1；nend；cpnfunction dist(a，b：integer)：longint； 計(jì)算第a條機(jī)器蛇和第b條機(jī)器蛇間的距離，若ab之間有屏蔽，則距離設(shè)為無窮大 nvarn i：integer；nbeginn dist：=oo；n for i：=1 to m do 如果a到b穿過第i個(gè)屏蔽，則返回?zé)o窮大 n if (cp(w1i，w2i，sa)*cp(w1i，w2i，sb)=-1) andn (cp(sa，sb，w1i)*cp(sa，sb，w2i)=-1