最小生成樹的算法

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

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

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

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

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

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

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

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

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

10、最小生成樹）;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) 所示，無向圖 G 是有權(quán)無向連通圖，求全部最小生成樹設(shè)由圖 1 (a) 得到一棵如圖1( b) 所示的最小生成樹稱基本回路是由樹枝和一條連枝組成的回路，由“破圈法”的思想，若此連枝是基本回路中的唯一最長邊，則將此邊去掉后得到約化圖無向圖G的基本回路中的唯一最長邊為：在基本回路-中有唯一最長邊是<1，7>，其權(quán)為7，將其去掉；在基本回路-中有唯一最長邊是<3，7&g

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

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

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

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

15、的補(bǔ)圖 ,然后再求出該補(bǔ)圖的補(bǔ)圖即得最小生成樹.（ 根據(jù)最小生成樹的定義易知 ）在尋找最小生成樹的補(bǔ)圖的過程中 ,遵循以下 2 條原則:原則一 , 度為 1 的結(jié)點(diǎn)的關(guān)聯(lián)邊肯定不在補(bǔ)圖中 ,刪去不管;原則二 ,環(huán)上的最大權(quán)邊一定在補(bǔ)圖中 ,保留在補(bǔ)圖中;循環(huán)利用上述原則 ,即可得到最小生成樹的補(bǔ)圖。例如 ,已知一個(gè)連通的帶權(quán)圖 G （見圖 1） ,要尋找其最小生成樹. 由圖 1知圖 G 有 11 條邊,8 個(gè)頂點(diǎn),從而它的最小生成樹的補(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;對產(chǎn)生的新圖,依此循環(huán)運(yùn)用 2 個(gè)原則處理,依次會把權(quán) 12 邊,權(quán) 9 邊, 權(quán)7 邊,權(quán) 6 邊放在補(bǔ)圖 GB（ 圖省略） 中,從而也就知最小生成樹中含有權(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的最小生成樹:1 ）判斷圖 G 是否有度為 1 的結(jié)點(diǎn),若無度為 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 的最小生成樹。3算法的正確性定理及復(fù)雜度分析 定理 :上述算法給出的 是原圖 G 的最小生成樹. 證明:由算法的過程知 是一棵含有 n -1 條邊的連通圖,所以一定是原圖 G 的一棵生成樹.假設(shè) =< V , E > 是原圖 G 的最小生成樹,則 中也含有 n -1 條邊;再記 的邊集為 ,若 = 則顯然 = ,即就是最小生成樹;若，則必定存在一條邊，而，把加到中 ,則在上產(chǎn)生一個(gè)環(huán) C,且在環(huán) C 上至少有一條邊不在中;下面在中刪去，加上,得新樹則 (