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

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

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

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

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

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

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

7、）、（）、（C C）是對圖（）是對圖（A A）分別進）分別進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的一棵生成樹，其權(quán)和分別為行深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的一棵生成樹，其權(quán)和分別為2020和和3333，前者比，前者比后者好一些，但并不是最小生成樹，最小生成樹的權(quán)和為后者好一些，但并不是最小生成樹，最小生成樹的權(quán)和為1919。 問題分析問題分析 出發(fā)點：具有出發(fā)點：具有n n個頂點的帶權(quán)連通圖，其對應(yīng)的生成樹有個頂點的帶權(quán)連通圖，其對應(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è)置一個頂點的集合設(shè)置一個頂點的集合S S和一個邊的集合和一個邊的集合TETE，S S和和TETE的初始狀態(tài)均為空集；的初始狀態(tài)均為空集；選定圖中的一個頂點選定圖中的一個頂點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)； 將頂點將頂點Y Y加入集合加入集合S S，邊（，邊（X X，Y Y）加入集合）加入集合TETE；得到最小生成樹得到最小生成樹T =T =（S S，TETE） 。 如何證明如何證明PrimPrim算法的正確性呢？提示：用反證法。算法的正確性呢？提示：用反證法。 因為操作是沿著邊進行的，所以數(shù)據(jù)結(jié)構(gòu)宜采用邊集數(shù)組表示法。因為操作是沿著邊進行的，所以數(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、個單元個單元 j:=elistk.endvj:=elistk.endv； jj為新加入的頂點為新加入的頂點 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算法的實現(xiàn)算法的實現(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、一條邊；若選取的邊使生成樹形成回路，的一條邊；若選取的邊使生成樹形成回路，則將其舍棄；如此進行下去，直到則將其舍棄；如此進行下去，直到TETE中包含中包含n-1n-1條邊為止。最后的條邊為止。最后的T T即為最小生成樹。即為最小生成樹。 如何證明呢？如何證明呢？ 最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 KruskalKruskal算法在實現(xiàn)過程中的關(guān)鍵和難點在于：如何判斷欲加入的一條邊算法在實現(xiàn)過程中的關(guān)鍵和難點在于：如何判斷欲加入的一條邊是否與生成樹中已保留的邊形成回路？是否與生成樹中已保留的邊形成回路？ 我們可以將頂點劃分到不同的集合中，每個集合中的頂點表示一個無回路我們可以將頂點劃分到

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

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

17、排好序； 設(shè)數(shù)組設(shè)數(shù)組C1.n-1C1.n-1用來存儲最小生成樹的所有邊，用來存儲最小生成樹的所有邊，CiCi是第是第i i次選取的可行邊在排好序的次選取的可行邊在排好序的elistelist中的下標(biāo)；中的下標(biāo)； 設(shè)一個數(shù)組設(shè)一個數(shù)組S1.nS1.n，SiSi都是集合，初始時都是集合，初始時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條邊，記下兩個頂點分屬的集合序號條邊，記下兩個頂點分屬的集合序號 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； 合并兩個集合合并兩個集合 sm2:= sm2:= ； 另一集合置空另一集合置空 EndEnd； j:=j+1j:=j+1； 取下條邊，繼續(xù)判斷取下條邊，繼續(xù)判斷 EndEnd； 輸出最小生成樹的各邊：輸出最小生成樹的各邊：elistelistCiCi KruskalKruskal算法的實現(xiàn)算法的實現(xiàn)最小生成樹算法及應(yīng)用最小生成樹算法及應(yīng)用 二、二、求圖的最小生成樹算法小結(jié)求圖的最小生成樹算法小結(jié) 都是基于貪心算法都是基于貪心算法時間復(fù)雜度均為時間復(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臺計算機，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺計算機被連接是指它們時臺計算機，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺計算機被連接是指它們時間有數(shù)據(jù)線連接。由于計算機所處的位置不同，因此不同的兩臺計算機的連接費用往往是不同的。間有數(shù)據(jù)線連接。由于計算機所處的位置不同，因此不同的兩臺計算機的連接費用往往是不同的。 當(dāng)然，如果將任意兩臺計算機都用數(shù)據(jù)線連接，費用將是相當(dāng)龐大的。為了節(jié)省費用，我們采用數(shù)據(jù)當(dāng)然，如果將任意兩臺計算機都用數(shù)據(jù)線連接

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