最小生成樹算法及應用.ppt

最小生成樹算法及應用,一、生成樹的概念,若圖是連通的無向圖或強連通的有向圖，則從圖中任意一個頂點出發(fā)調(diào)用一次bfs或dfs后，便可以系統(tǒng)地訪問圖中所有頂點；若圖是有根的有向圖，則從根出發(fā)通過調(diào)用一次dfs或bfs，亦可系統(tǒng)地訪問所有頂點。在這種情況下，圖中所有頂點加上遍歷過程中經(jīng)過的邊所構(gòu)成的子圖，稱為原圖的生成樹。,對于不連通的無向圖和不是強連通的有向圖，若有根或者從根外的任意頂點出發(fā)，調(diào)用一次bfs或dfs后，一般不能系統(tǒng)地訪問所有頂點，而只能得到以出發(fā)點為根的連通分支（或強連通分支）的生成樹。要訪問其它頂點，還需要從沒有訪問過的頂點中找一個頂點作為起始點，再次調(diào)用bfs或dfs，這樣得到的是生成森林。,由此可以看出，一個圖的生成樹是不唯一的，不同的搜索方法可以得到不同的生成樹，即使是同一種搜索方法，出發(fā)點不同亦可導致不同的生成樹。,可以證明：具有n個頂點的帶權連通圖，其對應的生成樹有n-1條邊。,最小生成樹算法及應用,最小生成樹算法及應用,二、求圖的最小生成樹算法,嚴格來說，如果圖G=（V，E）是一個連通的無向圖，則把它的全部頂點V和一部分邊E構(gòu)成一個子圖G，即G=（V， E），且邊集E能將圖中所有頂點連通又不形成回路，則稱子圖G是圖G的一棵生成樹。,對于帶權連通圖，生成樹的權即為生成樹中所有邊上的權值總和，權值最小的生成樹，稱為圖的最小生成樹。,求圖的最小生成樹具有很高的實際應用價值，比如下面的這個例題。,最小生成樹算法及應用,例1、城市公交網(wǎng) 問題描述 有一張城市地圖，圖中的頂點為城市，無向邊代表兩個城市間的連通關系，邊上的權為在這兩個城市之間修建高速公路的造價，研究后發(fā)現(xiàn)，這個地圖有一個特點，即任一對城市都是連通的?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設計可使得工程的總造價最少。 輸入 n（城市數(shù)，1=n=100）； e（邊數(shù)）； 以下e行，每行3個數(shù)i,j,wij，表示在城市i,j之間修建高速公路的造價。 輸出 n-1行，每行為兩個城市的序號，表明這兩個城市間建一條高速公路。,最小生成樹算法及應用,舉例 下面的圖（A）表示一個5個城市的地圖，圖（B）、（C）是對圖（A）分別進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的一棵生成樹，其權和分別為20和33，前者比后者好一些，但并不是最小生成樹，最小生成樹的權和為19。,問題分析 出發(fā)點：具有n個頂點的帶權連通圖，其對應的生成樹有n-1條邊！ 那么選哪n-1條邊呢？ 設圖G的度為n，G=（V，E） 我們介紹兩種基于貪心的算法，Prim算法和Kruskal算法。,最小生成樹算法及應用,1、用Prim算法求最小生成樹的思想如下： 設置一個頂點的集合S和一個邊的集合TE，S和TE的初始狀態(tài)均為空集； 選定圖中的一個頂點K，從K開始生成最小生成樹，將K加入到集合S； 重復下列操作，直到選取了n-1條邊： 選取一條權值最小的邊（X，Y），其中XS，not (YS)； 將頂點Y加入集合S，邊（X，Y）加入集合TE； 得到最小生成樹T =（S，TE） 。,如何證明Prim算法的正確性呢？提示：用反證法。 因為操作是沿著邊進行的，所以數(shù)據(jù)結(jié)構(gòu)宜采用邊集數(shù)組表示法。,最小生成樹算法及應用, 從文件中讀入圖的鄰接矩陣g； 邊集數(shù)組elist初始化； For i:=1 To n-1 Do Begin elisti.fromv:=1；elisti.endv:=i+1；elisti.weight:=g1,i+1； End； 求出最小生成樹的n-1條邊； For k:=1 To n-1 Do Begin min:=maxint；m:=k； For j:=k To n-1 Do 查找權值最小的一條邊 If elistj.weightk Then Begin t:=elistk；elistk:=elistm；elistm:=t；End； 把權值最小的邊調(diào)到第k個單元 j:=elistk.endv； j為新加入的頂點 For i:=k+1 To n-1 Do 修改未加入的邊集 Begin s:=elisti.endv； w:=gj,s； If welisti.weight Then Begin elisti.weight:=w；elisti.fromv:=j；End； End； End； 輸出；,Prim算法的實現(xiàn),最小生成樹算法及應用,2、用Kruskal算法求最小生成樹的思想如下： 設最小生成樹為T=（V，TE），設置邊的集合TE的初始狀態(tài)為空集。將圖G中的邊按權值從小到大排好序，然后從小的開始依次選取，若選取的邊使生成樹T不形成回路，則把它并入TE中，保留作為T的一條邊；若選取的邊使生成樹形成回路，則將其舍棄；如此進行下去，直到TE中包含n-1條邊為止。最后的T即為最小生成樹。,如何證明呢？,最小生成樹算法及應用,Kruskal算法在實現(xiàn)過程中的關鍵和難點在于：如何判斷欲加入的一條邊是否與生成樹中已保留的邊形成回路？ 我們可以將頂點劃分到不同的集合中，每個集合中的頂點表示一個無回路的連通分量，很明顯算法開始時，把所有n個頂點劃分到n個集合中，每個集合只有一個頂點，表明頂點之間互不相通。當選取一條邊時，若它的兩個頂點分屬于不同的集合，則表明此邊連通了兩個不同的連通分量，因每個連通分量無回路，所以連通后得到的連通分量仍不會產(chǎn)生回路，因此這條邊應該保留，且把它們作為一個連通分量，即把它的兩個頂點所在集合合并成一個集合。如果選取的一條邊的兩個頂點屬于同一個集合，則此邊應該舍棄，因為同一個集合中的頂點是連通無回路的，若再加入一條邊則必然產(chǎn)生回路。,就是并查集的思想。,最小生成樹算法及應用, 將圖的存儲結(jié)構(gòu)轉(zhuǎn)換成邊集數(shù)組表示的形式elist，并按照權值從小到大排好序； 設數(shù)組C1n-1用來存儲最小生成樹的所有邊，Ci是第i次選取的可行邊在排好序的elist中的下標； 設一個數(shù)組S1n，Si都是集合，初始時Si= i 。 i:=1；獲取的第i條最小生成樹的邊 j:=1；邊集數(shù)組的下標 While im2 Then Begin 找到的elist第j條邊滿足條件，作為第i條邊保留 Ci:=j；i:=i+1； sm1:=sm1+sm2；合并兩個集合 sm2:= ； 另一集合置空 End； j:=j+1； 取下條邊，繼續(xù)判斷 End； 輸出最小生成樹的各邊：elistCi,Kruskal算法的實現(xiàn),最小生成樹算法及應用,二、求圖的最小生成樹算法小結(jié),都是基于貪心算法,時間復雜度均為O（n*n）,Prim算法和Kruskal算法,三、應用舉例 例2、最優(yōu)布線問題（wire.?） 學校有n臺計算機，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺計算機被連接是指它們時間有數(shù)據(jù)線連接。由于計算機所處的位置不同，因此不同的兩臺計算機的連接費用往往是不同的。 當然，如果將任意兩臺計算機都用數(shù)據(jù)線連接，費用將是相當龐大的。為了節(jié)省費用，我們采用數(shù)據(jù)的間接傳輸手段，即一臺計算機可以間接的通過若干臺計算機（作為中轉(zhuǎn)）來實現(xiàn)與另一臺計算機的連接。 現(xiàn)在由你負責連接這些計算機，你的任務是使任意兩臺計算機都連通（不管是直接的或間接的）。 輸入格式 輸