1、.,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)地訪問所有頂點(diǎn)，而只能得到以出發(fā)點(diǎn)為根的連通分支（或強(qiáng)連通分支）的生成樹。要訪問其它頂點(diǎn)，還需要從沒有訪問過的頂點(diǎn)中找一個(gè)頂點(diǎn)作為起始點(diǎn)，再次調(diào)用bfs或dfs，

2、這樣得到的是生成森林。,由此可以看出，一個(gè)圖的生成樹是不唯一的，不同的搜索方法可以得到不同的生成樹，即使是同一種搜索方法，出發(fā)點(diǎn)不同亦可導(dǎo)致不同的生成樹。,可以證明：具有n個(gè)頂點(diǎn)的帶權(quán)連通圖，其對(duì)應(yīng)的生成樹有n-1條邊。,.,2,最小生成樹算法及應(yīng)用,.,3,最小生成樹算法及應(yīng)用,二、求圖的最小生成樹算法,嚴(yán)格來(lái)說(shuō)，如果圖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)值最小的生成樹，稱為圖的最小生成樹。,求圖的

3、最小生成樹具有很高的實(shí)際應(yīng)用價(jià)值，比如下面的這個(gè)例題。,.,4,最小生成樹算法及應(yīng)用,例1、城市公交網(wǎng)問題描述有一張城市地圖，圖中的頂點(diǎn)為城市，無(wú)向邊代表兩個(gè)城市間的連通關(guān)系，邊上的權(quán)為在這兩個(gè)城市之間修建高速公路的造價(jià)，研究后發(fā)現(xiàn)，這個(gè)地圖有一個(gè)特點(diǎn)，即任一對(duì)城市都是連通的?，F(xiàn)在的問題是，要修建若干高速公路把所有城市聯(lián)系起來(lái)，問如何設(shè)計(jì)可使得工程的總造價(jià)最少。輸入n（城市數(shù)，1=n=100）；e（邊數(shù)）；以下e行，每行3個(gè)數(shù)i,j,wij，表示在城市i,j之間修建高速公路的造價(jià)。輸出n-1行，每行為兩個(gè)城市的序號(hào)，表明這兩個(gè)城市間建一條高速公路。,.,5,最小生成樹算法及應(yīng)用,舉例下面的圖（

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

5、直到選取了n-1條邊：選取一條權(quán)值最小的邊（X，Y），其中XS，not(YS)；將頂點(diǎn)Y加入集合S，邊（X，Y）加入集合TE；得到最小生成樹T=（S，TE）。,如何證明Prim算法的正確性呢？提示：用反證法。因?yàn)椴僮魇茄刂呥M(jìn)行的，所以數(shù)據(jù)結(jié)構(gòu)宜采用邊集數(shù)組表示法。,.,7,最小生成樹算法及應(yīng)用,從文件中讀入圖的鄰接矩陣g；邊集數(shù)組elist初始化；Fori:=1Ton-1DoBeginelisti.fromv:=1；elisti.endv:=i+1；elisti.weight:=g1,i+1；End；求出最小生成樹的n-1條邊；Fork:=1Ton-1DoBeginmin:=maxint；m

6、:=k；Forj:=kTon-1Do查找權(quán)值最小的一條邊Ifelistj.weightkThenBegint:=elistk；elistk:=elistm；elistm:=t；End；把權(quán)值最小的邊調(diào)到第k個(gè)單元j:=elistk.endv；j為新加入的頂點(diǎn)Fori:=k+1Ton-1Do修改未加入的邊集Begins:=elisti.endv；w:=gj,s；Ifwelisti.weightThenBeginelisti.weight:=w；elisti.fromv:=j；End；End；End；輸出；,Prim算法的實(shí)現(xiàn),.,8,最小生成樹算法及應(yīng)用,2、用Kruskal算法求最小生成樹的思

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

8、個(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ú)回路的，若再加入一條邊則必然產(chǎn)生回路。,就是并查集的思想。,.,10,最小生成樹算法及應(yīng)用,將圖的存儲(chǔ)結(jié)構(gòu)轉(zhuǎn)換成邊集數(shù)組表示的形式elist，并按照權(quán)值從小到大排好序；設(shè)數(shù)組C1.n-1用來(lái)存儲(chǔ)最小生成樹的所有邊，Ci是第i次選取的可行邊在排好序的e

9、list中的下標(biāo)；設(shè)一個(gè)數(shù)組S1.n，Si都是集合，初始時(shí)Si=i。i:=1；獲取的第i條最小生成樹的邊j:=1；邊集數(shù)組的下標(biāo)Whileim2ThenBegin找到的elist第j條邊滿足條件，作為第i條邊保留Ci:=j；i:=i+1；sm1:=sm1+sm2；合并兩個(gè)集合sm2:=；另一集合置空End；j:=j+1；取下條邊，繼續(xù)判斷End；輸出最小生成樹的各邊：elistCi,Kruskal算法的實(shí)現(xiàn),.,11,最小生成樹算法及應(yīng)用,二、求圖的最小生成樹算法小結(jié),都是基于貪心算法,時(shí)間復(fù)雜度均為O（n*n）,Prim算法和Kruskal算法,三、應(yīng)用舉例例2、最優(yōu)布線問題（wire.?）

10、學(xué)校有n臺(tái)計(jì)算機(jī)，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來(lái)。兩臺(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)）來(lái)實(shí)現(xiàn)與另一臺(tái)計(jì)算機(jī)的連接?，F(xiàn)在由你負(fù)責(zé)連接這些計(jì)算機(jī)，你的任務(wù)是使任意兩臺(tái)計(jì)算機(jī)都連通（不管是直接的或間接的）。輸入格式輸入文件第一行為整數(shù)n（2=n0thencp：=1elsecp：=-1；end；cpfunctiondist(a，b：integer)：longin

11、t；計(jì)算第a條機(jī)器蛇和第b條機(jī)器蛇間的距離，若ab之間有屏蔽，則距離設(shè)為無(wú)窮大vari：integer；begindist：=oo；fori：=1tomdo如果a到b穿過第i個(gè)屏蔽，則返回?zé)o窮大if(cp(w1i，w2i，sa)*cp(w1i，w2i，sb)=-1)and(cp(sa，sb，w1i)*cp(sa，sb，w2i)=-1)thenexit；dist：=sqr(sa.x-sb.x)+sqr(sa.y-sb.y)；end；dist,.,17,beginread(n)；讀入數(shù)據(jù)fori：=1tondowithsidoread(x，y)；read(m)；fori：=1tomdoread(w

12、1i.x，w1i.y，w2i.x，w2i.y)；用Prim算法求最小生成樹fillchar(ba，sizeof(ba)，0)；所有機(jī)器蛇未訪問fori：=2tondodi：=oo；最短邊長(zhǎng)序列初始化d1：=0；ans：=0；從機(jī)器蛇1出發(fā),通信網(wǎng)的最短長(zhǎng)度初始化fori：=1tondobegin訪問n條機(jī)器蛇min：=oo；在所有未訪問的機(jī)器蛇中尋找與已訪問的機(jī)器蛇相連且具有最短邊長(zhǎng)的機(jī)器蛇kforj：=1tondoifnotbajand(djmin)thenbegink：=j；min：=dj；end；thenifmin=oothenbeginans：=-1；break；end；then若這樣