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

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

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

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

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

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

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

7、），其中X∈S，not (Y∈S)； 將頂點(diǎn)Y加入集合S，邊（X，Y）加入集合TE；④得到最小生成樹T =（S，TE） 。,如何證明Prim算法的正確性呢？提示：用反證法。 因?yàn)椴僮魇茄刂呥M(jìn)行的，所以數(shù)據(jù)結(jié)構(gòu)宜采用邊集數(shù)組表示法。,最小生成樹算法及應(yīng)用,① 從文件中讀入圖的鄰接矩陣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個(gè)單元} j:=elist[k].endv； {j為新加入的頂點(diǎn)} 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算法的實(shí)現(xiàn),最小生成樹算法及應(yīng)用,2、用Kruskal算法求最小生成樹的思想如下： 設(shè)最小生成樹為T=（V，TE），設(shè)置邊的集合TE的初始狀態(tài)為空集。將圖G中的邊

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

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

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

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

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

16、為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺(tái)計(jì)算機(jī)被連接是指它們時(shí)間有數(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ù)的間接傳輸手段，即一臺(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ī)都連通（不管是直接的或間接

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

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

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

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

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

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

23、 boolean； { 機(jī)器蛇的訪問標(biāo)志} d：array[1..maxn] of longint； {d[i]以機(jī)器蛇i為頭的最短邊長(zhǎng)} min：longint； ans：double；,function cp(p1，p2，p：TPoint)：integer； { 計(jì)算矢量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；{ 計(jì)算第a條機(jī)器蛇和第b條機(jī)器蛇間的距離，若ab之間有屏蔽，則距離設(shè)為無(wú)窮大 }var i：integer；begi

25、n dist：=oo； for i：=1 to m do { 如果a到b穿過第i個(gè)屏蔽，則返回?zé)o窮大 } 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)； {所有機(jī)器蛇未訪問} for i：

27、=2 to n do d[i]：=oo； {最短邊長(zhǎng)序列初始化} d[1]：=0 ；ans：=0； {從機(jī)器蛇1出發(fā),通信網(wǎng)的最短長(zhǎng)度初始化} for i：=1 to n do begin {訪問n條機(jī)器蛇} min：=oo；{在所有未訪問的機(jī)器蛇中尋找與已訪問的機(jī)器蛇相連且具有最短邊長(zhǎng)的機(jī)器蛇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}{若這樣的機(jī)器蛇不存在，則無(wú)解退出} ans：=ans+sqrt(min)； ba[k]：=true； {最短邊長(zhǎng)計(jì)入通信網(wǎng),機(jī)器蛇k已訪問} for j：=1 to n do {機(jī)器蛇k出發(fā)的所有不受屏蔽的邊中，尋找邊長(zhǎng)最短的（k