最小生成樹算法及應用

1、最小生成樹算法及應用,一、生成樹的概念,若圖是連通的無向圖或強連通的有向圖，則從圖中任意一個頂點出發(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)地訪問所有

2、頂點，而只能得到以出發(fā)點為根的連通分支（或強連通分支）的生成樹。要訪問其它頂點，還需要從沒有訪問過的頂點中找一個頂點作為起始點，再次調(diào)用bfs或dfs，這樣得到的是生成森林。,由此可以看出，一個圖的生成樹是不唯一的，不同的搜索方法可以得到不同的生成樹，即使是同一種搜索方法，出發(fā)點不同亦可導致不同的生成樹。,可以證明：具有n個頂點的帶權(quán)連通圖，其對應的生成樹有n-1條邊。,最小生成樹算法及應用,最小生成樹算法及應用,二、求圖的最小生成樹算

3、法,嚴格來說，如果圖G=（V，E）是一個連通的無向圖，則把它的全部頂點V和一部分邊E’構(gòu)成一個子圖G’，即G’=（V， E’），且邊集E’能將圖中所有頂點連通又不形成回路，則稱子圖G’是圖G的一棵生成樹。,對于帶權(quán)連通圖，生成樹的權(quán)即為生成樹中所有邊上的權(quán)值總和，權(quán)值最小的生成樹，稱為圖的最小生成樹。,求圖的最小生成樹具有很高的實際應用價值，比如下面的這個例題。,最小生成樹算法及應用,例1、城市公交網(wǎng)[問題描述] 有一張城市地

4、圖，圖中的頂點為城市，無向邊代表兩個城市間的連通關系，邊上的權(quán)為在這兩個城市之間修建高速公路的造價，研究后發(fā)現(xiàn)，這個地圖有一個特點，即任一對城市都是連通的。現(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來，問如何設計可使得工程的總造價最少。 [輸入] n（城市數(shù)，1<=n<=100）； e（邊數(shù)）； 以下e行，每行3個數(shù)i,j,wij，表示在城市i,j之間修建高速公路的造價。

5、60;[輸出] n-1行，每行為兩個城市的序號，表明這兩個城市間建一條高速公路。,最小生成樹算法及應用,[舉例] 下面的圖（A）表示一個5個城市的地圖，圖（B）、（C）是對圖（A）分別進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的一棵生成樹，其權(quán)和分別為20和33，前者比后者好一些，但并不是最小生成樹，最小生成樹的權(quán)和為19。,[問題分析] 出發(fā)點：具有n個頂點的帶權(quán)連通圖，其對應的生成樹有n-1條邊！

6、 那么選哪n-1條邊呢？ 設圖G的度為n，G=（V，E） 我們介紹兩種基于貪心的算法，Prim算法和Kruskal算法。,最小生成樹算法及應用,1、用Prim算法求最小生成樹的思想如下：①設置一個頂點的集合S和一個邊的集合TE，S和TE的初始狀態(tài)均為空集；②選定圖中的一個頂點K，從K開始生成最小生成樹，將K加入到集合S；③重復下列操作，直到選取了n-1條邊： 選取一條權(quán)值最小的邊（X，Y

7、），其中X∈S，not (Y∈S)； 將頂點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 elist[i].fromv:=1；e

8、list[i].endv:=i+1；elist[i].weight:=g[1,i+1]； End；③ 求出最小生成樹的n-1條邊； For k:=1 To n-1 Do Begin min:=maxint；m:=k； For j:=k To n-1 Do {查找權(quán)值最小的一條邊} If elist[j].weightk Then Begin t:=el

9、ist[k]；elist[k]:=elist[m]；elist[m]:=t；End； {把權(quán)值最小的邊調(diào)到第k個單元} j:=elist[k].endv； {j為新加入的頂點} For i:=k+1 To n-1 Do {修改未加入的邊集} Begin s:=elist[i].endv； w:=g[j,s]；

10、 If w<elist[i].weight Then Begin elist[i].weight:=w；elist[i].fromv:=j；End； End； End；④ 輸出；,——Prim算法的實現(xiàn),最小生成樹算法及應用,2、用Kruskal算法求最小生成樹的思想如下： 設最小生成樹為T=（V，TE），設置邊的集合TE的初始狀態(tài)為空集。將圖G中的邊

11、按權(quán)值從小到大排好序，然后從小的開始依次選取，若選取的邊使生成樹T不形成回路，則把它并入TE中，保留作為T的一條邊；若選取的邊使生成樹形成回路，則將其舍棄；如此進行下去，直到TE中包含n-1條邊為止。最后的T即為最小生成樹。,如何證明呢？,最小生成樹算法及應用,Kruskal算法在實現(xiàn)過程中的關鍵和難點在于：如何判斷欲加入的一條邊是否與生成樹中已保留的邊形成回路？ 我們可以將頂點劃分到不同的集合中，每個集合中的頂點表示一個無回

12、路的連通分量，很明顯算法開始時，把所有n個頂點劃分到n個集合中，每個集合只有一個頂點，表明頂點之間互不相通。當選取一條邊時，若它的兩個頂點分屬于不同的集合，則表明此邊連通了兩個不同的連通分量，因每個連通分量無回路，所以連通后得到的連通分量仍不會產(chǎn)生回路，因此這條邊應該保留，且把它們作為一個連通分量，即把它的兩個頂點所在集合合并成一個集合。如果選取的一條邊的兩個頂點屬于同一個集合，則此邊應該舍棄，因為同一個集合中的頂點是連通無回路的，若再

13、加入一條邊則必然產(chǎn)生回路。,就是并查集的思想。,最小生成樹算法及應用,① 將圖的存儲結(jié)構(gòu)轉(zhuǎn)換成邊集數(shù)組表示的形式elist，并按照權(quán)值從小到大排好序；② 設數(shù)組C[1..n-1]用來存儲最小生成樹的所有邊，C[i]是第i次選取的可行邊在排好序的elist中的下標；③ 設一個數(shù)組S[1..n]，S[i]都是集合，初始時S[i]= [ i ]。    i:=1；{獲取的第i條最小生成樹的邊

14、} j:=1；{邊集數(shù)組的下標} While im2 Then Begin {找到的elist第j條邊滿足條件，作為第i條邊保留} C[i]:=j；i:=i+1； s[m1]:=s[m1]+s[m2]；{合并兩個集合} s[m2]:=[ ]； {另一集合置空}

15、 End； j:=j+1； {取下條邊，繼續(xù)判斷} End； ④ 輸出最小生成樹的各邊：elist[C[i]],——Kruskal算法的實現(xiàn),最小生成樹算法及應用,二、求圖的最小生成樹算法小結(jié),都是基于貪心算法,時間復雜度均為O（n*n）,Prim算法和Kruskal算法,三、應用舉例例2、最優(yōu)布線問題（wire.???） 學校有n臺計算機，

16、為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺計算機被連接是指它們時間有數(shù)據(jù)線連接。由于計算機所處的位置不同，因此不同的兩臺計算機的連接費用往往是不同的。 當然，如果將任意兩臺計算機都用數(shù)據(jù)線連接，費用將是相當龐大的。為了節(jié)省費用，我們采用數(shù)據(jù)的間接傳輸手段，即一臺計算機可以間接的通過若干臺計算機（作為中轉(zhuǎn)）來實現(xiàn)與另一臺計算機的連接。 現(xiàn)在由你負責連接這些計算機，你的任務是使任意兩臺計算機都連通（不管是直接的或間接

17、的）。[輸入格式] 輸入文件第一行為整數(shù)n（2<=n<=100），表示計算機的數(shù)目。此后的n行，每行n個整數(shù)。 第x+1行y列的整數(shù)表示直接連接第x臺計算機和第y臺計算機的費用。[輸出格式] 輸出文件只有一個整數(shù)，表示最小的連接費用。[樣例輸入] [樣例輸出]3 2（注：表示連接1和2，2和3，費用為2）0

18、 1 21 0 12 1 0,機器蛇,在未來的某次戰(zhàn)爭中，我軍計劃了一次軍事行動，目的是劫持敵人的航母。由于這個計劃高度保密，你只知道你所負責的一部分：機器蛇的通信網(wǎng)絡。計劃中要將數(shù)百條機器蛇投放到航母的各個角落里。由于航母內(nèi)部艙室、管線錯綜復雜，且大部分由金屬構(gòu)成，因此屏蔽效應十分強烈，況且還要考慮敵人的大強度電子干擾，如何保持機器蛇間的聯(lián)系，成了一大難題。每條機器蛇的戰(zhàn)斗位置由作戰(zhàn)計劃部門制定，將會及時通知你。每條機器蛇上都帶有

19、接收、發(fā)射系統(tǒng)，可以同時與多條機器蛇通訊。由于整個系統(tǒng)承載的數(shù)據(jù)量龐大，需要一個固定的通訊網(wǎng)絡。情報部門提供了極其詳盡的敵方航母圖紙，使你對什么地方有屏蔽了如指掌。 請你設計一個程序，根據(jù)以上信息構(gòu)造通訊網(wǎng)絡，要求信息可以在任意兩條機器蛇間傳遞，同時為了避免干擾，通訊網(wǎng)絡的總長度要盡可能的短。,【輸入】輸入數(shù)據(jù)的第一行是一個整數(shù)n（n≤200）表示參戰(zhàn)的機器蛇總數(shù)。以下n行，每行兩個整數(shù)xi，yi，為第i支機器蛇的戰(zhàn)斗

20、位置。接下來一行是一個整數(shù)m（m≤100）表示航母內(nèi)部可能產(chǎn)生屏蔽的位置。最后m行，每行四個整數(shù)ai，bi，ci，di，表示線段(ai，bi)-(ci，di)處可能有屏蔽，也就是說通訊網(wǎng)絡不能跨越這條線段。【輸出】輸出數(shù)據(jù)應僅包括一個實數(shù)，表示建立的通訊網(wǎng)的最短長度，保留3位小數(shù)。如果不能成功建立通訊網(wǎng)，請輸出-1.000。,算法分析,題目中要求信息可以在任意兩條機器蛇間傳遞、通訊網(wǎng)絡的總長度要盡可能的短，顯然這是一個求圖的最

21、小生成樹問題。這道題在構(gòu)造圖的過程中還涉及到一點計算幾何的知識。1、判斷線段相交 兩條線段AB、CD，相交的充要條件是：A、B在直線CD的異側(cè)且C、D在直線AB的異側(cè)。也就是說從AC到AD的方向與從BC到BD的方向不同，從CA到CB的方向也與從DA到DB的方向不同。,2、套用最小生成樹的經(jīng)典算法求解,以機器蛇為頂點，以不受屏蔽的通信線路為邊構(gòu)建圖，就可以直接套用最小生成樹的經(jīng)典算法求解。由于幾乎每兩條機器蛇間都會有一條邊，因此

22、應選用Prim算法。 設const maxn=200 ； oo=2000000000；{ 機器蛇數(shù)的上限和無窮大}type TPoint=record {坐標} x，y：longint； end；var s，w1，w2：array[1..maxn] of TPoint； { 機器蛇的坐標和屏蔽線的坐標 } n，m，i，j，k：integer； ba：array[1..maxn] of

23、 boolean； { 機器蛇的訪問標志} d：array[1..maxn] of longint； {d[i]以機器蛇i為頭的最短邊長} min：longint； ans：double；,function cp(p1，p2，p：TPoint)：integer； { 計算矢量PP1*PP2 }var v：longint；be

24、gin v：=(p1.x-p.x)*(p2.y-p.y)-(p1.y-p.y)*(p2.x-p.x)； if v=0 then cp：=0 else if v>0 then cp：=1 else cp：=-1；end；{cp}function dist(a，b：integer)：longint；{ 計算第a條機器蛇和第b條機器蛇間的距離，若ab之間有屏蔽，則距離設為無窮大 }var i：integer；begi

25、n dist：=oo； for i：=1 to m do { 如果a到b穿過第i個屏蔽，則返回無窮大 } if (cp(w1[i]，w2[i]，s[a])*cp(w1[i]，w2[i]，s[b])=-1) and (cp(s[a]，s[b]，w1[i])*cp(s[a]，s[b]，w2[i])=-1) then exit； dist：=sqr(s[a].x-s[b].x)+sqr(s[a].y-s[b]

26、.y)；end；{ dist },begin read(n)；{ 讀入數(shù)據(jù) } for i：=1 to n do with s[i] do read(x，y)； read(m)； for i：=1 to m do read(w1[i].x，w1[i].y，w2[i].x，w2[i].y)；{用Prim算法求最小生成樹 } fillchar(ba，sizeof(ba)，0)； {所有機器蛇未訪問} for i：

27、=2 to n do d[i]：=oo； {最短邊長序列初始化} d[1]：=0 ；ans：=0； {從機器蛇1出發(fā),通信網(wǎng)的最短長度初始化} for i：=1 to n do begin {訪問n條機器蛇} min：=oo；{在所有未訪問的機器蛇中尋找與已訪問的機器蛇相連且具有最短邊長的機器蛇k} for j：=1 to n do if not ba[j] and (d[j]<min) then begi

28、n k：=j； min：=d[j]； end；{then} if min=oo then begin ans：=-1； break； end；{then}{若這樣的機器蛇不存在，則無解退出} ans：=ans+sqrt(min)； ba[k]：=true； {最短邊長計入通信網(wǎng),機器蛇k已訪問} for j：=1 to n do {機器蛇k出發(fā)的所有不受屏蔽的邊中，尋找邊長最短的（k