最小生成樹(shù)的算法

1、最小生成樹(shù)的算法王潔引言：求連通圖的最小生成樹(shù)是數(shù)據(jù)結(jié)構(gòu)中討論的一個(gè)重要問(wèn)題在現(xiàn)實(shí)生活中，經(jīng)常遇到如何得到連通圖的最小生成樹(shù)，求最小生成樹(shù)不僅是圖論的基本問(wèn)題之一 ,在實(shí)際工作中也有很重要的意義，,人們總想尋找最經(jīng)濟(jì)的方法將一個(gè)終端集合通過(guò)某種方式將其連接起來(lái) ,比如將多個(gè)城市連為公路網(wǎng)絡(luò) ,要設(shè)計(jì)最短的公路路線;為了解決若干居民點(diǎn)供水問(wèn)題 ,要設(shè)計(jì)最短的自來(lái)水管路線等.而避開(kāi)這些問(wèn)題的實(shí)際意義 ,抓住它們的數(shù)學(xué)本質(zhì) ,就表現(xiàn)為最小生成樹(shù)的構(gòu)造。下面將介紹幾種最小生成樹(shù)的算法。一，用“破圈法”求全部最小生成樹(shù)的算法 1 理論根據(jù)1.1 約化原則給定一無(wú)向連通圖 G =（V,E）（ V 表示頂點(diǎn)

2、，E表示邊），其中 V= , , ,E= , , 對(duì)于 G 中的每條邊 e E都賦予權(quán)（ ）>0，求生成樹(shù) T = （V,H），H E，使生成樹(shù)所有邊權(quán)最小，此生成樹(shù)稱(chēng)為最小生成樹(shù)（1） 基本回路將屬于生成樹(shù) T 中的邊稱(chēng)為樹(shù)枝，樹(shù)枝數(shù)為n -1，不屬于生成樹(shù)的邊稱(chēng)為連枝將任一連枝加到生成樹(shù)上后都會(huì)形成一條回路把這種回路稱(chēng)為基本回路，記為?；净芈肥怯?T 中的樹(shù)枝和一條連枝構(gòu)成的回路（2） 基本割集設(shè)無(wú)向圖 G 的割集 S （割集是把連通圖分成兩個(gè)分離部分的最少支路集合） ，若 S 中僅包含有T中的一條樹(shù)枝，則稱(chēng)此割集為基本割集，記為。基本割集是集合中的元素只有一條是樹(shù)枝，其他的為連枝

3、（3） 等長(zhǎng)變換 設(shè)T=(V,H),為一棵生成樹(shù)，e H, E, H,當(dāng)且僅當(dāng)，也就是說(shuō)e ，則=Te, 也是一棵生成樹(shù)。當(dāng)=時(shí)，這棵生成樹(shù)叫做等長(zhǎng)變換。等長(zhǎng)變換就是從基本回路中選取與樹(shù)枝等權(quán)邊，并與此樹(shù)枝對(duì)換后形成的生成樹(shù)根據(jù)以上定理得出2個(gè)結(jié)論：若在某個(gè)回路C 中有一條唯一的最長(zhǎng)邊，則任何一棵最小生成樹(shù)都不含這條邊；若在某個(gè)邊 e 的割集中有一條唯一最短邊，則每棵生成樹(shù)中都必須含這條邊由上面結(jié)論可以得到唯一性：若圖 G 中的生成樹(shù)T = （V,H）是唯一的一棵最小生成樹(shù)，當(dāng)且僅當(dāng)任意一連枝e H, E 都是其基本回路中唯一最長(zhǎng)邊，任意一條樹(shù)邊 e 都是其基本割集中的唯一最短邊由此在最小生成

4、樹(shù)不唯一的情況下，就可以得到一個(gè)約化的原則：假設(shè)已得到一棵最小生成樹(shù)。對(duì)于中每一條樹(shù)邊e H，若 e 是基本割集中唯一的最短邊，則每棵最小生成樹(shù)中一定包含此邊，則把此邊取為固定邊，并將此邊的基本割集去掉。對(duì)于每條連枝e H, E，若它是基本回路中唯一最長(zhǎng)邊，則每棵生成樹(shù)中都不會(huì)包含此條連枝，則將其消去約化原則是在最小生成樹(shù)不唯一的情況下，從已經(jīng)得到的一棵最小生成樹(shù)中選出其樹(shù)枝是基本割集中唯一的最短邊，則每一棵最小生成樹(shù)中必含有此邊，就取為固定邊在基本回路中若有一條唯一最長(zhǎng)邊，則每棵最小生成樹(shù)都不含此條邊，將其去掉通過(guò)這樣約化后再求最小生成樹(shù)，計(jì)算量會(huì)大大下降1.2 全部最小生成樹(shù)設(shè)是已求得的一

5、棵最小生成樹(shù)，在最小生成樹(shù)不唯一的情況下，存在其他最小生成樹(shù) T，稱(chēng)T-得到的邊集的長(zhǎng)度為距離（這里的長(zhǎng)度是指集合中元素的個(gè)數(shù)）。為了簡(jiǎn)單起見(jiàn)，設(shè)最小生成樹(shù)的邊集為 , , ，對(duì)于的任何邊集= , , （），則每棵最小生成樹(shù) T 與的距離是一定的，或?yàn)?，或?yàn)? ，或?yàn)?n -1這樣我們就可以按所有的最小生成樹(shù)與的距離來(lái)分類(lèi)。記= , , 為所有的即不含的最小生成樹(shù)的集合（可能為空）對(duì)于其它的最小生成樹(shù)T而言，=T為換出邊，=T為入邊，中的邊叫不動(dòng)邊若 T 有 k 個(gè)換出邊就說(shuō)它與的距離為 k當(dāng) k=0 時(shí)為參考樹(shù)本身。當(dāng) k = 1 時(shí)，對(duì)任意的，有。最小生成樹(shù)是用基本割集的邊 p 換出的邊

6、且邊p 的權(quán)和邊的權(quán)相等。當(dāng) k = 2時(shí)，。在換入一條邊后得到的生成樹(shù)中再換入一條邊，即換入兩條邊后得到的一棵最小生成樹(shù)。以此遞推下去，可建立如下關(guān)系：此遞推關(guān)系表示在換入k 1條邊后得到的生成樹(shù)中再換入一條邊后得到的一棵最小生成樹(shù)用此遞推關(guān)系，就可以求出全部的最小生成樹(shù)。2 算法 選取一棵最小生成樹(shù)，求出 的全部基本回路對(duì)每一個(gè)基本回路去掉唯一最大邊，約化所給的圖然后對(duì)應(yīng)于 的每條樹(shù)邊，求出基本割集若此樹(shù)邊也是基本割集中唯一最短邊，則取其為固定邊，并將此基本割集作上記號(hào)，求其他的最小生成樹(shù)時(shí)，就不用考慮此割集了其余的基本割集，應(yīng)用遞推關(guān)系，對(duì)應(yīng)于遞推式求出所有的換入邊對(duì)于距離為1的，每一個(gè)

7、換入邊對(duì)應(yīng)著一棵最小生成樹(shù)；對(duì)于距離為2 的每?jī)蓚€(gè)換入邊也對(duì)應(yīng)著一棵最小生成樹(shù)；換入 k 條邊，就對(duì)應(yīng)著距離為 k 的最小生成樹(shù)以此類(lèi)推就可以求出全部的最小生成樹(shù)求無(wú)向圖 G 的全部最小生成樹(shù)的算法如下（1） 求最小生成樹(shù) 比較成熟的算法，在此就不做介紹（2） 求約化圖算法 （去掉基本回路中的唯一最長(zhǎng)邊）Step1 令為連枝集合，j=1；Step2 在 中加入連枝，形成一個(gè)基本回路，記為；Step 3 若 是基本回路中唯一最長(zhǎng)邊，則從圖 G 中去掉；Step4 j =j +1,若 j 不大于 b，則返回Step2；Step5 輸出經(jīng)約化后的圖 G。（3 ）求固定邊算法 （保留基本割集中唯一的最

8、短邊）Step 1 令 E = , , 為最小生成樹(shù)的樹(shù)枝集合，S =，為樹(shù)枝的基本割集，i=1;Step 2 從約化后的圖 G 中求出樹(shù)枝的基本割集；Step3 若 是基本割集 S 中的唯一最短邊，則將 取為固定邊，并對(duì)作記號(hào)； Step4 i 增加1, 若 i 不等于n, 則返回Step2（4） 求換入邊算法（ 若基本割集中有記號(hào)，則為固定邊，若沒(méi)有記號(hào)，則從中求換入邊）Step1 設(shè) H 為換入邊的集合，F(xiàn) 為換出邊的集合，初始 H、F 為空，i=1；Step 2 若的基本割集 =中有記號(hào)，則 為固定邊，執(zhí)行Step 8；Step3 若的基本割集 中無(wú)記號(hào)，則 放入 F 中；Step4

9、令 k= 1；Step 5 若，且權(quán)，放入H中；Step6 k =k+ 1；Step7 若 k < d （d 為 的長(zhǎng)度，即中元素的個(gè)數(shù)） 則返回Step5；Step 8 i = i +1，若 i 小于或等于 n 1, 則返回Step 2（5） 求全部最小生成樹(shù)算法 按距離從1到g 求全部最小生成樹(shù)）設(shè) H =為換入邊的集合，F(xiàn) =為換出邊的集合Step 1 若 H 為空，則最小生成樹(shù)是唯一，輸出，算法結(jié)束( )Step2 k =1, = , 輸出 , （k 為距離） ；Step3 j =k；Step4 若, 且權(quán)，則在中用代替，輸出（在已經(jīng)換入 k 條邊后的最小生成樹(shù)中再換入，生成新的

10、最小生成樹(shù)）;Step 5 j = j +1，若 j小于或等于m，重復(fù)上面的Step 4；Step 6 k = k + 1，若 k 小于或等于 g，則返回Step 3；Step7 結(jié)束3 應(yīng)用舉例例 如圖1 (a) 所示，無(wú)向圖 G 是有權(quán)無(wú)向連通圖，求全部最小生成樹(shù)設(shè)由圖 1 (a) 得到一棵如圖1( b) 所示的最小生成樹(shù)稱(chēng)基本回路是由樹(shù)枝和一條連枝組成的回路，由“破圈法”的思想，若此連枝是基本回路中的唯一最長(zhǎng)邊，則將此邊去掉后得到約化圖無(wú)向圖G的基本回路中的唯一最長(zhǎng)邊為：在基本回路-中有唯一最長(zhǎng)邊是<1，7>，其權(quán)為7，將其去掉；在基本回路-中有唯一最長(zhǎng)邊是<3，7&g

11、t;，其權(quán)為3，將其去掉；在基本回路-中有唯一最長(zhǎng)邊是<5，7>，其權(quán)為4，將其去掉；在基本回路-中有唯一最長(zhǎng)邊是<1，6>，其權(quán)為 8，將其去掉去掉基本回路中的唯一最長(zhǎng)的邊后，形成如圖1 (c) 所示的約化圖對(duì)無(wú)向圖 G 進(jìn)行約化后，最小生成樹(shù) 中各邊的基本割集為：<1，2>：<1，2> ，<1，2>為唯一最短邊，取為固定邊，將此割集作上記號(hào)；<2，7>：<2，7>，<2，3> ；<6，7>：<6，7>，<5，4>；<6，5>：<6，5>

12、，<5，4>，<6，5>為唯一最短邊，取為固定邊，將此割集作上記號(hào)；<4，3>：<4，3>，<2，3> ，<4，3>為唯一最短邊，取為固定邊，將此割集作上記號(hào)；<7，4>：<7，4>，<2，3>，<5，4> ，<7，4>為唯一最短邊，取為固定邊，將此割集作上記號(hào)在 中，取為固定邊的有 <1，2>，<6，5>，<7，4>，<4，3> 這樣其他的最小生成樹(shù)只能在 <2，7>，<2，3> 和 <

13、;6，7>，<5，4> 這兩個(gè)基本割集中選取了根據(jù)算法，得到換入邊為 <2，3>，<5，4> ，換出邊為 <2，7>，<6，7> 當(dāng) k = 1 時(shí)，換入一條邊得到的最小生成樹(shù)W(<2，7> )=w（<2，3>），用邊<2，3>換<2，7>得到最小生成樹(shù)a，如圖1（ d） 所示；w （<6，7>） =w （<5，4>），用<5，4>換<6，7>得到最小生成樹(shù)b，如圖1 （e ）所示； k =2 時(shí)，用<2，3>換<2

14、，7>后，再用<5，4>換<6，7>得到的最小生成樹(shù)c，如圖1 （f） 所示 4 結(jié)論本文在對(duì)連通圖的特征進(jìn)行分析的基礎(chǔ)上，得出在某個(gè)基本回路 C 中有一條唯一的最長(zhǎng)邊，則任何一棵最小生成樹(shù)都不含這條邊，將此邊從無(wú)向圖 G 中去掉，對(duì)圖進(jìn)行約化；若在某個(gè)邊 e的割集中有一條唯一最短邊，則每棵生成樹(shù)中都必須含這條邊，則取為固定邊利用“破圈法”的思想去掉基本回路中的唯一最長(zhǎng)邊，保留基本割集中唯一最短邊，對(duì)連通圖進(jìn)行約化，在約化圖的基礎(chǔ)上求全部最小生成樹(shù)，計(jì)算量會(huì)大量地下降，算法的效率將大大地提高二，尋找最小生成樹(shù)的補(bǔ)圖算法1 例談補(bǔ)圖算法思想補(bǔ)圖算法首先尋找最小生成樹(shù)

15、的補(bǔ)圖 ,然后再求出該補(bǔ)圖的補(bǔ)圖即得最小生成樹(shù).（ 根據(jù)最小生成樹(shù)的定義易知 ）在尋找最小生成樹(shù)的補(bǔ)圖的過(guò)程中 ,遵循以下 2 條原則:原則一 , 度為 1 的結(jié)點(diǎn)的關(guān)聯(lián)邊肯定不在補(bǔ)圖中 ,刪去不管;原則二 ,環(huán)上的最大權(quán)邊一定在補(bǔ)圖中 ,保留在補(bǔ)圖中;循環(huán)利用上述原則 ,即可得到最小生成樹(shù)的補(bǔ)圖。例如 ,已知一個(gè)連通的帶權(quán)圖 G （見(jiàn)圖 1） ,要尋找其最小生成樹(shù). 由圖 1知圖 G 有 11 條邊,8 個(gè)頂點(diǎn),從而它的最小生成樹(shù)的補(bǔ)圖有且只有 4 條邊. 算法步驟如下:第 1 步:根據(jù)原則一 ,因?yàn)?deg （） =1,所以刪去權(quán) 3 邊,得圖 2;第2 步:根據(jù)原則一,刪去權(quán) 10 邊得

16、圖 3;第3 步:根據(jù)原則二,把權(quán) 12 邊放在補(bǔ)圖 GB（ 圖省略） 中得圖 4;第4 步:根據(jù)原則一,刪去權(quán) 11 邊得圖 5;對(duì)產(chǎn)生的新圖,依此循環(huán)運(yùn)用 2 個(gè)原則處理,依次會(huì)把權(quán) 12 邊,權(quán) 9 邊, 權(quán)7 邊,權(quán) 6 邊放在補(bǔ)圖 GB（ 圖省略） 中,從而也就知最小生成樹(shù)中含有權(quán) 2邊,權(quán) 3 邊,權(quán) 4 邊,權(quán) 5 邊,權(quán) 8 邊,權(quán) 10 邊,權(quán) 11 邊,如圖6 所示. 2 算法描述 設(shè) G =< V , E, f >是一具有 n 個(gè)結(jié)點(diǎn) m 條邊的連通有權(quán)圖,構(gòu)造 G的最小生成樹(shù):1 ）判斷圖 G 是否有度為 1 的結(jié)點(diǎn),若無(wú)度為 1 的結(jié)點(diǎn),轉(zhuǎn) 3） ;若有度

17、為 1 的結(jié)點(diǎn),去掉與之相關(guān)聯(lián)的邊,得新圖記為 ;2 ）把 賦予 G, 轉(zhuǎn) 1）3 ）把G 中所有環(huán)中的一條最大權(quán)邊放入 GB 中,得新圖 ;4 ）記數(shù)GB 中邊的條數(shù),當(dāng) GB 中邊的條數(shù)小于 m -（ n -1）時(shí)，把賦予 G ,轉(zhuǎn) 1），若 GB 中邊的條數(shù)等于 m - （n -1 ）時(shí),跳出循環(huán);)5）求出 GB 的補(bǔ)圖,記為 ; 就是原圖 G 的最小生成樹(shù)。3算法的正確性定理及復(fù)雜度分析 定理 :上述算法給出的 是原圖 G 的最小生成樹(shù). 證明:由算法的過(guò)程知 是一棵含有 n -1 條邊的連通圖,所以一定是原圖 G 的一棵生成樹(shù).假設(shè) =< V , E > 是原圖 G 的最小生成樹(shù),則 中也含有 n -1 條邊;再記 的邊集為 ,若 = 則顯然 = ,即就是最小生成樹(shù);若，則必定存在一條邊，而，把加到中 ,則在上產(chǎn)生一個(gè)環(huán) C,且在環(huán) C 上至少有一條邊不在中;下面在中刪去，加上,得新樹(shù)則 (