|
最小耗費(fèi)生成樹 在例1 - 2及1 - 3中已考察過這個(gè)問題。因?yàn)榫哂衝 個(gè)頂點(diǎn)的無(wú)向網(wǎng)絡(luò)G的每個(gè)生成樹剛好具有n-1條邊，所以問題是用某種方法選擇n-1條邊使它們形成G的最小生成樹。至少可以采用三種不同的貪婪策略來選擇這n-1條邊。這三種求解最小生成樹的貪婪算法策略是： K r u s k a l算法，P r i m算法和S o l l i n算法。 1. Kruskal算法 (1) 算法思想 K r u s k a l算法每次選擇n- 1條邊，所使用的貪婪準(zhǔn)則是：從剩下的邊中選擇一條不會(huì)產(chǎn)生環(huán)路的具有最小耗費(fèi)的邊加入已選擇的邊的集合中。注意到所選取的邊若產(chǎn)生環(huán)路則不可能形成一棵生成樹。K r u s k a l算法分e 步，其中e 是網(wǎng)絡(luò)中邊的數(shù)目。按耗費(fèi)遞增的順序來考慮這e 條邊，每次考慮一條邊。當(dāng)考慮某條邊時(shí)，若將其加入到已選邊的集合中會(huì)出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。 考察圖1-12a 中的網(wǎng)絡(luò)。初始時(shí)沒有任何邊被選擇。圖13-12b 顯示了各節(jié)點(diǎn)的當(dāng)前狀態(tài)。邊（ 1 , 6）是最先選入的邊，它被加入到欲構(gòu)建的生成樹中，得到圖1 3 - 1 2 c。下一步選擇邊（ 3，4）并將其加入樹中（如圖1 3 - 1 2 d所示）。然后考慮邊( 2，7 )，將它加入樹中并不會(huì)產(chǎn)生環(huán)路，于是便得到圖1 3 - 1 2 e。下一步考慮邊（ 2，3）并將其加入樹中（如圖1 3 - 1 2 f所示）。在其余還未考慮的邊中，（7，4）具有最小耗費(fèi)，因此先考慮它，將它加入正在創(chuàng)建的樹中會(huì)產(chǎn)生環(huán)路，所以將其丟棄。此后將邊（ 5，4）加入樹中，得到的樹如圖13-12g 所示。下一步考慮邊（ 7，5），由于會(huì)產(chǎn)生環(huán)路，將其丟棄。最后考慮邊（ 6，5）并將其加入樹中，產(chǎn)生了一棵生成樹，其耗費(fèi)為9 9。圖1 - 1 3給出了K r u s k a l算法的偽代碼。 / /在一個(gè)具有n 個(gè)頂點(diǎn)的網(wǎng)絡(luò)中找到一棵最小生成樹 令T為所選邊的集合，初始化T= 令E 為網(wǎng)絡(luò)中邊的集合 w h i l e(E≠ )&&(| T |≠n- 1 ) { 令(u,v)為E中代價(jià)最小的邊 E=E- { (u,v) } / /從E中刪除邊 i f( (u,v)加入T中不會(huì)產(chǎn)生環(huán)路)將（ u,v）加入T } i f(| T | = =n-1) T是最小耗費(fèi)生成樹 e l s e 網(wǎng)絡(luò)不是互連的，不能找到生成樹 圖13-13 Kruskao算法的偽代碼 (2) 正確性證明 利用前述裝載問題所用的轉(zhuǎn)化技術(shù)可以證明圖1 3 - 1 3的貪婪算法總能建立一棵最小耗費(fèi)生成樹。需要證明以下兩點(diǎn)： 1) 只要存在生成樹，K r u s k a l算法總能產(chǎn)生一棵生成樹； 2) 產(chǎn)生的生成樹具有最小耗費(fèi)。令G為任意加權(quán)無(wú)向圖（即G是一個(gè)無(wú)向網(wǎng)絡(luò)）。從1 2 . 11 . 3節(jié)可知當(dāng)且僅當(dāng)一個(gè)無(wú)向圖連通時(shí)它有生成樹。而且在Kruskal 算法中被拒絕（丟棄）的邊是那些會(huì)產(chǎn)生環(huán)路的邊。刪除連通圖環(huán)路中的一條邊所形成的圖仍是連通圖，因此如果G在開始時(shí)是連通的，則T與E中的邊總能形成一個(gè)連通圖。也就是若G開始時(shí)是連通的，算法不會(huì)終止于E= 和| T |< n- 1。 現(xiàn)在來證明所建立的生成樹T具有最小耗費(fèi)。由于G具有有限棵生成樹，所以它至少具有一棵最小生成樹。令U為這樣的一棵最小生成樹， T與U都剛好有n- 1條邊。如果T=U, 則T就具有最小耗費(fèi)，那么不必再證明下去。因此假設(shè)T≠U，令k(k >0) 為在T中而不在U中的邊的個(gè)數(shù)，當(dāng)然k 也是在U中而不在T中的邊的數(shù)目。 通過把U變換為T來證明U與T具有相同的耗費(fèi)，這種轉(zhuǎn)化可在k 步內(nèi)完成。每一步使在T而不在U中的邊的數(shù)目剛好減1。而且U的耗費(fèi)不會(huì)因?yàn)檗D(zhuǎn)化而改變。經(jīng)過k 步的轉(zhuǎn)化得到的U將與原來的U具有相同的耗費(fèi)，且轉(zhuǎn)化后U中的邊就是T中的邊。由此可知， T具有最小耗費(fèi)。每步轉(zhuǎn)化包括從T中移一條邊e 到U中，并從U中移出一條邊f(xié)。邊e 與f 的選取按如下方式進(jìn)行： 1) 令e 是在T中而不在U中的具有最小耗費(fèi)的邊。由于k >0，這條邊肯定存在。 2) 當(dāng)把e 加入U(xiǎn)時(shí)，則會(huì)形成唯一的一條環(huán)路。令f 為這條環(huán)路上不在T中的任意一條邊。 由于T中不含環(huán)路，因此所形成的環(huán)路中至少有一條邊不在T中。 從e 與f 的選擇方法中可以看出， V=U+ {e} -{ f } 是一棵生成樹，且T中恰有k- 1條邊不在V中出現(xiàn)?，F(xiàn)在來證明V的耗費(fèi)與U的相同。顯然，V的耗費(fèi)等于U的耗費(fèi)加上邊e 的耗費(fèi)再減去邊f(xié) 的耗費(fèi)。若e 的耗費(fèi)比f(wàn) 的小，則生成樹V的耗費(fèi)比U的耗費(fèi)小，這是不可能的。如果e 的耗費(fèi)高于f，在K r u s k a l算法中f 會(huì)在e 之前被考慮。由于f 不在T中，Kruskal 算法在考慮f 能否加入T時(shí)已將f 丟棄，因此f 和T中耗費(fèi)小于或等于f 的邊共同形成環(huán)路。通過選擇e，所有這些邊均在U中，因此U肯定含有環(huán)路，但是實(shí)際上這不可能，因?yàn)閁是一棵生成樹。e 的代價(jià)高于f 的假設(shè)將會(huì)導(dǎo)致矛盾。剩下的唯一的可能是e 與f 具有相同的耗費(fèi)，由此可知V與U的耗費(fèi)相同。 (3) 數(shù)據(jù)結(jié)構(gòu)的選擇及復(fù)雜性分析 為了按耗費(fèi)非遞減的順序選擇邊，可以建立最小堆并根據(jù)需要從堆中一條一條地取出各邊。當(dāng)圖中有e 條邊時(shí)，需花(e) 的時(shí)間初始化堆及O ( l o ge) 的時(shí)間來選取每一條邊。邊的集合T與G中的頂點(diǎn)一起定義了一個(gè)由至多n 個(gè)連通子圖構(gòu)成的圖。用頂點(diǎn)集合來描述每個(gè)子圖，這些頂點(diǎn)集合沒有公共頂點(diǎn)。為了確定邊（ u,v）是否會(huì)產(chǎn)生環(huán)路，僅需檢查u,v 是否在同一個(gè)頂點(diǎn)集中（即處于同一子圖）。如果是，則會(huì)形成一個(gè)環(huán)路；如果不是，則不會(huì)產(chǎn)生環(huán)路。因此對(duì)于頂點(diǎn)集使用兩個(gè)F i n d操作就足夠了。當(dāng)一條邊包含在T中時(shí)，2個(gè)子圖將被合并成一個(gè)子圖，即對(duì)兩個(gè)集合執(zhí)行U n i o n操作。集合的F i n d和U n i o n操作可利用8 . 1 0 . 2節(jié)的樹（以及加權(quán)規(guī)則和路徑壓縮）來高效地執(zhí)行。F i n d操作的次數(shù)最多為2e，Un i o n操作的次數(shù)最多為n- 1（若網(wǎng)絡(luò)是連通的，則剛好是n- 1次）。加上樹的初始化時(shí)間，算法中這部分的復(fù)雜性只比O (n+e) 稍大一點(diǎn)。 對(duì)集合T所執(zhí)行的唯一操作是向T中添加一條新邊。T可用數(shù)組t 來實(shí)現(xiàn)。添加操作在數(shù)組 的一端進(jìn)行，因?yàn)樽疃嗫稍赥中加入n- 1條邊，因此對(duì)T的操作總時(shí)間為O (n)。 總結(jié)上述各個(gè)部分的執(zhí)行時(shí)間，可得圖1 3 - 1 3算法的漸進(jìn)復(fù)雜性為O (n+el o ge)。 (4) 實(shí)現(xiàn) 利用上述數(shù)據(jù)結(jié)構(gòu)，圖1 - 1 3可用C + +代碼來實(shí)現(xiàn)。首先定義E d g e N o d e類（見程序1 3 - 6 )，它是最小堆的元素及生成樹數(shù)組t 的數(shù)據(jù)類型 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 19:42:37 b 等級(jí)：職業(yè)俠客 文章：470 積分：956 門派：黑客帝國(guó) 注冊(cè)：2003-8-28 第 12 樓 程序13-6 Kruskal算法所需要的數(shù)據(jù)類型 template <class T> class EdgeNode { p u b l i c : operator T() const {return weight;} p r i v a t e : T weight;//邊的高度 int u, v;//邊的端點(diǎn) } ; 為了更簡(jiǎn)單地使用8 . 1 0 . 2節(jié)的查找和合并策略，定義了U n i o n F i n d類，它的構(gòu)造函數(shù)是程序8 - 1 6的初始化函數(shù)，U n i o n是程序8 - 1 6的加權(quán)合并函數(shù)，F(xiàn) i n d是程序8 - 1 7的路徑壓縮搜索函數(shù)。 為了編寫與網(wǎng)絡(luò)描述無(wú)關(guān)的代碼，還定義了一個(gè)新的類U N e t Wo r k，它包含了應(yīng)用于無(wú)向網(wǎng)絡(luò)的所有函數(shù)。這個(gè)類與U n d i r e c t e d類的差別在于U n d i r e c t e d類中的函數(shù)不要求加權(quán)邊，而U N e t Wo r k要求邊必須帶有權(quán)值。U N e t Wo r k中的成員需要利用N e t w o r k類中定義的諸如B e g i n和N e x t Ve r t e x的遍歷函數(shù)。不過，新的遍歷函數(shù)不僅需要返回下一個(gè)鄰接的頂點(diǎn)，而且要返回到達(dá)這個(gè)頂點(diǎn)的邊的權(quán)值。這些遍歷函數(shù)以及有向和無(wú)向加權(quán)網(wǎng)絡(luò)的其他函數(shù)一起構(gòu)成了W N e t w o r k類（見程序1 3 - 7）。 程序13-7 WNetwork類 template<class T> class WNetwork : virtual public Network { public : virtual void First(int i, int& j, T& c)=0; virtual void Next(int i, int& j, T& c)=0; } ; 象B e g i n和N e x t Ve r t e x一樣，可在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h類中加入函數(shù)F i r s t與N e x t。現(xiàn)在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h類都需要從W N e t Wo r k中派生而來。由于A d j a c e n c y W G r a p h類和L i n k e d W G r a p h類需要訪問U N e t w o r k的成員，所以這兩個(gè)類還必須從U N e t Wo r k中派生而來。U N e t Wo r k : : K r u s k a l的代碼見程序1 3 - 8，它要求將Edges() 定義為N e t Work 類的虛成員，并且把U N e t Wo r k定義為E d g e N o d e的友元）。如果沒有生成樹，函數(shù)返回f a l s e，否則返回t r u e。注意當(dāng)返回true 時(shí)，在數(shù)組t 中返回最小耗費(fèi)生成樹。 程序13-8 Kr u s k a l算法的C + +代碼 template<class T> bool UNetwork<T>::Kruskal(EdgeNode<T> t[]) {// 使用K r u s k a l算法尋找最小耗費(fèi)生成樹 // 如果不連通則返回false // 如果連通，則在t [ 0 : n - 2 ]中返回最小生成樹 int n = Ve r t i c e s ( ) ; int e = Edges(); / /設(shè)置網(wǎng)絡(luò)邊的數(shù)組 InitializePos(); // 圖遍歷器 EdgeNode<T> *E = new EdgeNode<T> [e+1]; int k = 0; // E的游標(biāo) for (int i = 1; i <= n; i++) { // 使所有邊附屬于i int j; T c; First(i, j, c); while (j) { // j 鄰接自i if (i < j) {// 添加到達(dá)E的邊 E[++k].weight = c; E[k].u = i; E[k].v = j;} Next(i, j, c); } } // 把邊放入最小堆 MinHeap<EdgeNode<T> > H(1); H.Initialize(E, e, e); UnionFind U(n); // 合并/搜索結(jié)構(gòu) // 根據(jù)耗費(fèi)的次序來抽取邊 k = 0; // 此時(shí)作為t的游標(biāo) while (e && k < n - 1) { // 生成樹未完成，尚有剩余邊 EdgeNode<T> x; H.DeleteMin(x); // 最小耗費(fèi)邊 e - - ; int a = U.Find(x.u); int b = U.Find(x.v); if (a != b) {// 選擇邊 t[k++] = x; U . U n i o n ( a , b ) ; } } D e a c t i v a t e P o s ( ) ; H . D e a c t i v a t e ( ) ; return (k == n - 1); } 2. Prim算法 與Kr u s k a l算法類似，P r i m算法通過每次選擇多條邊來創(chuàng)建最小生成樹。選擇下一條邊的貪婪準(zhǔn)則是：從剩余的邊中，選擇一條耗費(fèi)最小的邊，并且它的加入應(yīng)使所有入選的邊仍是一棵樹。最終，在所有步驟中選擇的邊形成一棵樹。相反，在Kruskal 算法中所有入選的邊集合最終形成一個(gè)森林。 P r i m算法從具有一個(gè)單一頂點(diǎn)的樹T開始，這個(gè)頂點(diǎn)可以是原圖中任意一個(gè)頂點(diǎn)。然后往T中加入一條代價(jià)最小的邊（ u , v）使TÈ{ (u , v) }仍是一棵樹，這種加邊的步驟反復(fù)循環(huán)直到T中包含n- 1條邊。注意對(duì)于邊（ u , v），u、v 中正好有一個(gè)頂點(diǎn)位于T中。P r i m算法的偽代碼如圖1 -1 4所示。在偽代碼中也包含了所輸入的圖不是連通圖的可能，在這種情況下沒有生成樹。圖1 - 1 5顯示了對(duì)圖1-12a 使用P r i m算法的過程。把圖1 - 1 4的偽代碼細(xì)化為C + +程序及其正確性的證明留作練習(xí)（練習(xí)3 1）。 / /假設(shè)網(wǎng)絡(luò)中至少具有一個(gè)頂點(diǎn) 設(shè)T為所選擇的邊的集合，初始化T= 設(shè)T V為已在樹中的頂點(diǎn)的集合，置T V= { 1 } 令E為網(wǎng)絡(luò)中邊的集合 w h i l e(E< > ) & & (| T | < > n-1) { 令（u , v）為最小代價(jià)邊，其中u T V, v T V i f（沒有這種邊） b re a k E=E- { (u,v) } / /從E中刪除此邊 在T中加入邊（ u , v） } if (| T | = =n- 1 ) T是一棵最小生成樹 else 網(wǎng)絡(luò)是不連通的，沒有最小生成樹 圖13-14 Prim最小生成樹算法 如果根據(jù)每個(gè)不在T V中的頂點(diǎn)v 選擇一個(gè)頂點(diǎn)n e ar (v)，使得n e ar (v) Î TV 且c o st (v, n e ar (v) )的值是所有這樣的n e ar (v) 節(jié)點(diǎn)中最小的，則實(shí)現(xiàn)P r i m算法的時(shí)間復(fù)雜性為O (n2 )。下一條添加到T中的邊是這樣的邊：其cost (v, near (v)) 最小，且v T V。 3. Sollin算法 S o l l i n算法每步選擇若干條邊。在每步開始時(shí)，所選擇的邊及圖中的n個(gè)頂點(diǎn)形成一個(gè)生成樹的森林。在每一步中為森林中的每棵樹選擇一條邊，這條邊剛好有一個(gè)頂點(diǎn)在樹中且邊的代價(jià)最小。將所選擇的邊加入要?jiǎng)?chuàng)建的生成樹中。注意一個(gè)森林中的兩棵樹可選擇同一條邊，因此必須多次復(fù)制同一條邊。當(dāng)有多條邊具有相同的耗費(fèi)時(shí)，兩棵樹可選擇與它們相連的不同的邊，在這種情況下，必須丟棄其中的一條邊。開始時(shí)，所選擇的邊的集合為空。若某一步結(jié)束時(shí)僅剩下一棵樹或沒有剩余的邊可供選擇時(shí)算法終止。 圖1 - 6給出了初始狀態(tài)為圖1-12a 時(shí)，使用S o l l i n算法的步驟。初始入選邊數(shù)為0時(shí)的情形如圖13-12a 時(shí),森林中的每棵樹均是單個(gè)頂點(diǎn)。頂點(diǎn)1，2，.，7所選擇的邊分別是(1.6), (2,7),(3,4), (4,3), (5,4), (6,1), (7,2)，其中不同的邊是( 1 , 6 )，( 2 , 7 )，(3,4) 和( 5 , 4 )，將這些邊加入入選邊的集合后所得到的結(jié)果如圖1 3 - 1 6 a所示。下一步具有頂點(diǎn)集{ 1 , 6 }的樹選擇邊( 6 , 5 )，剩下的兩棵樹選擇邊( 2 , 3 )，加入這兩條邊后已形成一棵生成樹，構(gòu)建好的生成樹見圖1 3 - 6 b。S o l l i n算法的C + +程序?qū)崿F(xiàn)及其正確性證明留作練習(xí)（練習(xí)3 2 )。 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); |
|
|
