計算機算法基礎 第2版 習題及答案 第9章

PAGE36第9章 圖的最小支撐樹以圖9-6為例，圖示用Kruskal算法逐步計算下面各圖的最小支撐樹。解：(a)aab66dfcg412810539137e(1)66adbfcg412810539137e(2)666adbfcg412810539137e(3)66adbfcg412810539137e(4)666adbfcg412810539137e(5)66adbfcg412810539137e(6)666adbfcg412810539137e(7)66adbfcg412810539137e(8)666adbfcg412810539137e(9)66adbfcg412810539137e(10)666adbfcg412810539137e(11)66adbfcg4537e(12)算法產生的MST(b)4412adbfcg7561114312910e13(1)h412adbfcg7561114312910e13(2)h4412adbfcg7561114312910e13(3)h412adbfcg7561114312910e13(4)h4412adbfcg7561114312910e13(5)h412adbfcg7561114312910e13(6)h4412adbfcg7561114312910e13(7)h412adbfcg7561114312910e13(8)h4412adbfcg7561114312910e13(9)h412adbfcg7561114312910e13(10)h4412adbfcg7561114312910e13(11)h412adbfcg7561114312910e13(12)h4412adbfcg75639e(13)最后的MSTh以圖9-8為例，圖示用Prim算法逐步計算下面各圖的最小支撐樹。我們假設起始點為a。66adbfcg5981010h4137e(b)88766116adbfcg498105h11137e(a)9677解：(a)66d=0=niladbfcg498105h11137e(0)初始化967d==nild==nild==nild==nild==nild==nild==nil76d=0=niladbfcg498105h11137e(1)選a，更新b，c，d，e967d=5=ad==nild==nild==nild=13=ad=6=ad=9=a766d=0=niladbfcg498105h11137e(2)選d，更新e，f967d=5=ad=11=dd==nild==nild=13=ad=6=ad=7=d76d=0=niladbfcg498105h11137e(3)選b，更新c967d=5=ad=11=dd==nild==nild=10=bd=6=ad=7=d766d=0=niladbfcg498105h11137e(4)選e，更新c，f，g967d=5=ad=9=ed==nild=6=ed=7=ed=6=ad=7=d76d=0=niladbfcg498105h11137e(5)選g，更新f，h967d=5=ad=8=gd=7=gd=6=ed=7=ed=6=ad=7=d766d=0=niladbfcg498105h11137e(6)選c，沒有更新點967d=5=ad=8=gd=7=gd=6=ed=7=ed=6=ad=7=d76d=0=niladbfcg498105h11137e(7)選h，更新f967d=5=ad=4=hd=7=gd=6=ed=7=ed=6=ad=7=d766d=0=niladbfcg498105h11137e(8)選f，沒有更新點967d=5=ad=4=hd=7=gd=6=ed=7=ed=6=ad=7=d7adbfcg45h7e(9)最后的MST，總權值為426776(b)66adbfcg5981010h4137e(0)初始化8876611d==nild==nild==nild==nild=0=nild==nild==nild==nil6adbfcg5981010h4137e(1)選a，更新b，c，g8876611d=10=ad==nild==nild==nild=0=nild=4=ad=11=ad==nil66adbfcg5981010h4137e(2)選c，更新b，d，g，h8876611d=9=cd==nild==nild=6=cd=0=nild=4=ad=10=cd=8=c6adbfcg5981010h4137e(3)選h，更新g，f8876611d=9=cd==nild=13=hd=6=cd=0=nild=4=ad=7=hd=8=c66adbfcg5981010h4137e(4)選g，更新e8876611d=9=cd=6=gd=13=hd=6=cd=0=nild=4=ad=7=hd=8=c(5)選e，更新b，d，f6adbfcg5981010h4137e8876611d=8=ed=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e66adbfcg5981010h4137e(6)選f，無更新點8876611d=8=ed=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e6adbfcg5981010h4137e(7)選d，更新b8876611d=7=dd=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e66adbfcg5981010h4137e(8)選b，無更新點8876611d=7=dd=6=gd=5=ed=6=cd=0=nild=4=ad=7=hd=6=e6adbfcg5h47e(9)最后的MST，總權值為41766我們知道，如果一圖中所有邊的權都一樣，那么任何一個支撐樹都是一個最小支撐樹并且可以用廣度優(yōu)先或者深度優(yōu)先算法求得?，F(xiàn)在，假設圖G(V,E)中邊的權不完全一樣，但是只有兩種，要么是w(>0)或者是2w。有個教授提出下面的算法：Smart-MST(G(V,E))在每一條有權2w的邊(u,v)中間插入一新點p，把邊(u,v)變成兩條邊，(u,p)和(p,v)，并給每條邊以權值w，即w(u,p)=w(p,v)=w。我們把這個改變后的圖記為G’。用BFS算出G’的支撐樹T’。把T’中所有在第一步新插入的點去掉，即再把(u,p)和(p,v)并為一條邊(u,v)。剩下的圖為G的MST。請證明這個算法正確或證明不正確。解：這個算法不正確。下面圖給出一反例。下圖(a)是原圖G，圖(b)是在每條權為2w的邊中插入一點后的圖G’，圖(c)是用BFS后得到的支撐樹T’。顯然，把插入點移走后的T’不是MST。ww2wwacbwwwacb·wwwacb·w(a)(b)(c)假設邊(u,v)是加權的連通圖G(V,E)中權值最小的一條邊。證明邊(u,v)一定會出現(xiàn)在某個最小支撐樹中。進一步，如果這條邊的權比任何其他的邊都絕對地小，即沒有另一與之權相等的邊，那么，任何一個最小支撐樹都含有這個邊。證明：考慮以頂點u為一邊的割C=({u},V-{u})。因為一開始的子集A為空集，那么這個割顯然尊重A。因為邊(u,v)的權最小，它必定是一個最小交叉邊，因而是一條安全邊。根據(jù)定理9.1，通用算法第一步就可把邊(u,v)選入集合A，所以這條邊一定會出現(xiàn)在某個最小支撐樹中。進一步，如果這條邊的權比任何其他的邊都絕對地小，那么，任何一個最小支撐樹都含有這個邊。我們可以用反證法來證。假設樹T是一個MST，它不含邊(u,v)。那么把邊(u,v)加到這個MST中后形成一回路(見下圖)。uuvxT是一個MSTy(u,v)T刪除回路上一條邊(x,y)后我們得到一個支撐樹T’，T’=T{(u,v)}-{(x,y)}。因為(u,v)權最小，w(u,v)<w(x,y)，所以有W(T’)=W(T)+w(u,v)-w(x,y)<W(T)。這與T是最小支撐樹相矛盾。所以，任何一個最小支撐樹都含有這個權最小的邊(u,v)。假設C是加權的連通圖G(V,E)中的一個回路，邊(u,v)是回路中權值最大的一條邊，那么一定會有某個最小支撐樹不含有邊(u,v)。證明： 假設T是連通圖G(V,E)的一個最小支撐樹。如果T不含有邊(u,v)，則證明完成。所以，為了用反證法，我們假定T含有邊(u,v)。現(xiàn)在，如果我們把邊(u,v)從T中刪除，則把T分裂為兩個不相交的子樹T1和T2，而且u和v分屬兩邊。不坊設uT1，vT2(見下圖(a))。再考慮把邊(u,v)從回路C中去掉后的路徑，P=C–{(u,v)}，它的兩端為u和v。如果我們沿著路徑P從頂點u到頂點v走的話，一定會碰上一條邊(x,y)使得xT1，yT2(見下圖(b))。顯然T’=(T–{(u,v)}{(x,y)}也是一個支撐樹。因為w(x,y)≤w(u,v)，我們有W(T’)=W(T)-w(u,v)+w(x,y)≤W(T)。所以T’也必定是一個最小支撐樹，否則矛盾。因為T’不含有邊(u,v)，命題得證。(a)設計一個計算加權連通圖G(V,E)的最小支撐樹T的算法使它含有圖中某一條指定的邊(a,b)。也就是說，T是所有含邊(a,b)的支撐樹中權值最小的一個。你需要證明其正確性。(b)設計一個計算加權連通圖G(V,E)的最小支撐樹T的算法使它含有圖中一個邊的子集A。其中，子集A不包含回路。也就是說，T是所有含子集A的支撐樹中權值最小的一個。你需要證明其正確性。解: (a)算法如下：MST-Variation-1(G(V,E),a,b) //邊(a,b)Ez?min{w(u,v)|(u,v)?E} //找出邊里面最小的權值zk?w(a,b) //k是邊(a,b)的權值，顯然有zkw(a,b)?z–1 //把邊(a,b)的權值改為z-1后，它的權值最小用Kruskal或Prim算法找出變更后的圖G’的MST //w(a,b)=z–1是唯一的變化w(a,b)?k //恢復w(a,b)原來的值returnMST //這個MST就是解正確性證明：考慮算法第4行中變更后的圖G’，它與圖G的唯一區(qū)別是邊(a,b)的權值不同。在圖G’中，邊(a,b)的權值是w’(a,b)=z–1。讓我們用T’表示圖G’的最小支撐樹；用T表示算法產生的支撐樹；用T*表示原圖G的任一個含邊(a,b)的支撐樹。我們需要證明：邊(a,b)一定在T中。W(T)W(T*)。先證明(1)。算法的第4行得到圖G’的最小支撐樹T’，因為w’(a,b)=z–1有最小的權值，習題4證明了邊(a,b)一定在T’中。為完整起見，這里再用反證法證一下。假設邊(a,b)不在T’中，那么刪去T’中從a到b的路徑上一條邊(x,y)，再把邊(a,b)加進來，就得到另一個支撐樹T’’(見下圖)。因為w’(a,b)=z–1<w(x,y)，所以有W(T’’)=W(T’)-w(x,y)+w’(a,b)<W(T’)。這與T’是MST矛盾，所以邊(a,b)一定在T’中，那么，也就在支撐樹T中了。接著，我們證明(2)。假設T*是原圖G的任何一個含邊(a,b)的支撐樹。如果我們把T*里的邊(a,b)的權值換為(z–1)，那么T*就變成一個G’的的支撐樹，但不一定是最小。因為T’是圖G’的MST，所以有W(T’)W(T*)–k+(z–1) (1)因為算法產生的支撐樹T是把T’中邊(a,b)的權值換為k，所以有W(T)=W(T’)+k-(z–1) (2)把式(1)代入式(2)，得 :W(T)=W(T’)+k-(z–1)(W(T*)–k+(z–1))+k-(z–1)=W(T*)。(b) 算法如下:MST-Variation-2(G(V,E),A)z?min{w(u,v)|(u,v)?E}G’(V’,E’)?G(V,E) //復制一個考貝A’?Aforeachedge(a’,b’)A’ w(a’,b’)?z–1 //把A’中，也就是A中每條邊的權值都變成z–1endfor用Kruskal或Prim算法找到圖G’的MST，記為T’T?foreachedge(a’,b’)inT’ TT{(a,b)} //T是原圖中同樣邊組成的樹endforreturnT End正確性證明：顯然，算法中，圖G’是把集合A中每一條邊的權值改為z-1而得到的。首先證明A’一定在T’中。如果其中有任何一條邊(a,b)A’不在T’中，那么把(a,b)加到T’中形成一回路。因為A’中邊不形成回路，回路中一定會有不在A’中邊。那么，和上面(a)部分證明一樣，把這條邊換為(a,b)后可得權更小的支撐樹而矛盾。所以A’T’。從而有AT。假設T*是原圖G中任一個含子集A的支撐樹。如果我們T*中子集A的每一條邊的權值改為z-1，那么我們就得到一個圖G’的支撐樹，但不一定最小。因為T’是G’的MST，所以有：W(T’)W(T*)-W(A)+|A|(z-1) (1)因為算法產生的支撐樹T是把T’中子集A的每一條邊的權值從z-1改為它原來的的權值，所以有：W(T)=W(T’)+W(A)-|A|(z-1) (2)把式(1)代入式(2)，得: W(T)=W(T’)+W(A)-|A|(z-1)(W(T*)-W(A)+|A|(z-1))+W(A)-|A|(z-1)=W(T*)。所以，算法產生的支撐樹T是所有含子集A的支撐樹中權值最小的一個。(a) T和T’是同一個連通圖G的兩個不同支撐樹。假設邊x是T的一條邊但不是T’里的邊。證明在T’中存在一條邊y不屬T，并且(T-{x}){y}和(T’-{y}){x}都是G的支撐樹。(b) 假設一個圖G的所有邊的權值都兩兩不等，證明它只能有唯一的一個最小支撐樹。證明：(a)假定x=(u，v)。如下圖(a)所示，把x從T里刪去后，T分裂為T1和T2兩個子樹，并且uT1和vT2。 讓V1表示T1中頂點的集合，V2表示T2中頂點的集合，那么C=(V1,V2)是一個割。如果我們沿著在T’中從頂點u到頂點v的路徑走的話，我們一定會碰到一條穿越這個割的交叉邊y=(a,b)使得aV1和bV2。顯然(T-{x}){y}構成一個支撐樹。把y從T’中刪去后，T’分裂為兩個子樹，頂點a和b分屬兩邊，并且頂點u和a在同一邊，v和b在同一邊，而邊x=(u,v)連接這兩個子樹。因此，(T’-{y}){x}也是一個支撐樹，證畢。(b) 我們用反證法。假設圖G有兩個不同的最小支撐樹T和T’。因為不同，一定有一條邊xT，但xT’。根據(jù)(a)題的結果，在T’中存在一條邊y不屬T，并且(T-{x}){y}和(T’-{y}){x}都是G支撐樹。因為G的所有邊的權都兩兩不等，w(x)w(y)。不失一般性，假設w(x)>w(y)。那么，T*=(T-{x}){y}的權值為W(T*)=W(T)–w(x)+w(y)<W(T)。這與T是一個最小支撐樹相矛盾。所以，圖G只能有唯一的一個最小支撐樹。假設圖G(V,E)的最小支撐樹是T。假設我們把圖中一條不在T中的某條邊(u,v)(T)的權減少。請設計一個O(n)算法，把T進行適當修改，從而得到對應於上述修改后圖的最小支撐樹。你需要證明你的算法的正確性。解: 假設邊(u,v)T的權w(u,v)減少為w*(u,v)<w(u,v)。修改后的圖的最小支撐樹可以用下面算法從T得到。MST-for-modified-graph(G,T,w*(u,v))沿著T里面從頂點u到頂點v的唯一路徑p(u,v)，逐條邊檢查找出權值最大的邊e。ifw(e)>w*(u,v) thenT*Tè{(u,v)}–{e} elseT*TendifreturnT*因為算法第一步可以對最小支撐樹T作一次從頂點u開始的DFS搜索實現(xiàn)，所以算法的復雜度為O(n)，這里n=|V|。正確性證明：顯然，算法輸出的T*是按題意修改后圖的一棵支撐樹。我們用W(T)表示原來圖的最小支撐樹的總權值，而用W(T*)表示上面算法產生的支撐樹的總權值。顯然，如果w(e)>w*(u,v)，我們有W(T*)=W(T)+w*(u,v)–w(e)<W(T)，否則有W(T*)=W(T)W(T)+w*(u,v)–w(e)。所以，任何情況下有：W(T*)W(T)和W(T*)W(T)+w*(u,v)–w(e) (1)假設Tmod是修改后的圖的任何一個支撐樹，我們證明W(T*)W(Tmod)。我們分兩種情況討論如下。Tmod不含邊(u,v)。如果是這種情況，Tmod也是圖未改動前的一個支撐樹，所以必有W(T)W(Tmod)。由上面(1)式，W(T*)W(T)，所以有W(T*)W(Tmod)。Tmod含有邊(u,v)。如果是這種情況，如下圖所示，我們把邊(u,v)從Tmod刪除以后會得到兩個不相交子樹T1和T2。那么，在原圖G的最小支撐樹T里面，從頂點u到頂點v的唯一路徑p(u,v)上一定含有一條邊(a,b)使得a?T1和b?T2。這條邊加上T1和T2也形成一個支撐圖T’={(a,b)}T1T2=Tmodè{(a,b)}–{(u,v)}，并且有關系W(T’)=W(Tmod)+w(a,b)-w*(u,v)。因為T’不含有邊(u,v)，它是原來圖中的一個支撐樹，所以有W(T)W(T’)，也就是，W(T)W(Tmod)+w(a,b)-w*(u,v) (2)由上面(1)式，我們有W(T*)W(T)+w*(u,v)–w(e)。把(2)式代入后，我們得到：W(T*)W(T)+w*(u,v)–w(e)[W(Tmod)+w(a,b)-w*(u,v)]+w*(u,v)–w(e)=W(Tmod)+w(a,b)-w(e)。W(Tmod) (因為邊e也在路徑p(u,v)上，且有w(e)w(a,b)。)這就證明了，對于按題意修改后的圖的任何一個支撐樹Tmod，都有W(T*)W(Tmod)。那么，T*必定是一棵修改后的圖的最小支撐樹。與最小支撐樹對稱的一個概念是最大支撐樹。一個加權連通圖的最大支撐樹就是具有最大權值的支撐樹。請設計一個時間復雜度好的，計算一個加權連通圖G(V,E)的最大支撐樹的算法。解: 一個簡單算法如下。Maximum-SP(G(V,E))從圖G構造圖G’。G’是把G中每條邊的權值加上負號取得。用Kruskal算法或Prim算法得到G’的最小支撐樹T’把T’中每條邊的權改回原來的值，即去掉每條邊上所加負號，得到圖G的支撐樹TReturnT因為同樣一個支撐樹T在圖G’中的權是它在圖G中的權取反，所以G’的最小支撐樹恰恰是G的最大支撐樹。所以算法正確。算法復雜度與最小支撐樹算法一樣。下面是兩個計算最小支撐樹的算法的偽碼。對每一個算法，如果正確，請證明其正確性，并討論如何有效地實現(xiàn)它；否則，用反例證明其不正確。我們假定圖G(V,E)是個加權連通圖。MST-A(G(V,E))Sortedgessuchthate1e2…emT?Efori1tom //按排好順序依次檢查每條邊 ifT–{ei}仍是一個連通圖 thenT?T–{ei} endifendforreturnTEndMST-B(G(V,E))T?foreachedgee,takeninarbitraryorder //以任意順序逐條邊檢查 ifTè{e}hasnocycles thenT?Tè{e} endifendforreturnTEnd解：(a)這個算法正確。我們先用歸納法證明，當算法每次從T中刪去一條邊e=(u,v)時，T–{e}仍然含有一個MST。歸納基礎：開始時，圖G(V,E)是個加權連通圖，含有一個MST。所以，在第3行的循環(huán)前，T=E含有一個MST。歸納步驟：假設算法從T中刪去k條邊后，k0，剩下的圖是T’并且含有一個MST?，F(xiàn)在證明，如果算法在圖T’中再刪去一條邊e’，T’–{e’}仍然含有一個MST。由算法知，T’–{e’}是個連通圖。這意味著T’中有一個含有e’的回路C’?？蓴喽?，回路中e’的權值最大。這是因為，如果回路中有比e’的權值大的邊，那么它應該在先前被檢查過并且被刪去。所以，根據(jù)第5題的結果，T’–{e’}含有一個MST。歸納成功。由上面證明的結果知，算法輸出的T含有一個MST。現(xiàn)在，我們只需證明，T是一棵樹即可。這是顯然的。首先，T是連通的，因為每一步都保證了T的連通性。第二，T必不含回路。否則，回路中權最大的邊在被檢查時未被刪去，與算法矛盾。因此，最后的T必定是一棵樹，那么它必定是一個MST，算法正確。這個算法的第一步可用任一已知的排序算法在O(mlgn)時間完成。檢查一個圖的連通性可以用BFS或DFS在O(m)時間完成。因為有m條邊要檢查，這樣做，算法需要O(m2)時間。(b)這個算法不正確。下圖給出一反例。下圖(a)是一個加權的連通圖。如果我們按順序(a,b),(b,c),(c,d),(d,a)檢查邊的話，會得到一個圖(b)中的支撐圖。這不是最小支撐樹。假設G(V，E)是一個加權的連通圖并有|V|=n,|E|=m。又設每條邊e上的權為1到W之間的某個整數(shù)，1w(e)W，這里W是一個正整數(shù)的常數(shù)。請設計一個復雜度為O(m)的算法計算圖G的最小支撐樹。解: 我們采用Prim算法但需要設計一個數(shù)據(jù)結構Q使得Extract-Min(Q)和更新d(v)可以很快。因為1w(e)W，所以d(v)[0,W]。我們把具有相同權值的頂點組織為一個集合或鏈表。具體來說，我們定義：L[k]={u|d(u)=k}(0￡k￡W)和L[W+1]={u|d(u)=￥}。我們用鏈表把每個集合中頂點鏈接起來。一開始，L[0]={s}，L[W+1]=V–{s}，L[k]=，k?{1,2,…,W}。這些鏈表的總和組成Q。每當算法需要做Extract-Min(Q)時，我們就順序搜索L[0]，L[1]，L[2]，…，直到找到一個非空的鏈表L[k]。那么，這個鏈表中任一頂點v的d(v)值等于k，并且必定是最小的。我們取出該鏈表中首項。這一步最多需要查看W+2個鏈表，時間為O(W)=O(1)。因總共需要做n次循環(huán)，這部分總時間為O(n)。當一個頂點u的d(u)值需要從k更新到p<k時，我們只需把頂點u從鏈表L[k]摘下來，然后掛到鏈表L[p]上去即可。因此每一次更新只需O(1)時間。因為我們需要最多2m次更新，所以算法的復雜度是O(n)+O(m)=O(m)。下面是該算法偽碼。Modified-Prim’s-Algorithm(G(V,E),s)foreachv?V d(v)?￥ p(v)?nil mark(v)F //表示點v還沒有加入到樹A中endfor d(s)?0A? ConstructT(V,A)fork1toW L[k]? //初始化鏈表，建立指向鏈表L[k]的指針，首項為空endforL[0]?{s}L[W+1]V–{s}forj1ton //循環(huán)n次，每次取一個頂點和一條邊 i?0 whileL[i]=? i?i+1 endwhile u?ExtractheadfromL[i] //從L[i]中刪除首項 A?Aè{(p(u),u)} //如果p(u)=nil，A不變，否則，A加一條安全邊 mark(u)T foreachv?Adj(u) ifmark(v)=Fandw(u,v)<d(v) //更新u的鄰居v then p(v)?u k?d(v) L[k]?L[k]-{v} //從L[k]中刪除點v d(v)?p?w(u,v) //更新d(v) L[p]?L[p]è{v} //在L[p]尾部插入點v endif endforendforreturnT(V,A)End根據(jù)上面討論，該算法的時間復雜度是O(m)。(最寬路徑問題)在加權連通圖G(V,E)的一條路徑上權值最小的一條邊稱為這條路徑的瓶頸，而這條路徑的寬度定義為它的一條瓶頸邊的權值。例如，下圖中路徑<a,b,e,g>的瓶頸是邊(b,e)，這條路徑的寬度為w(b,e)=7。圖G(V,E)中從頂點u到頂點v的所有路徑中寬度最大的一條路徑稱為從u到v的最寬路徑。例如下圖中從a到g的最寬路徑是<a,b,c,d,f,g>，其寬度是8。假設T是G(V,E)的最大支撐樹(定義見第9題)，證明T中任意兩點之間的路徑都是G(V,E)中這兩點間的最寬路徑。證明：為了用反證法證明，假設P(u,v)是T中一條從頂點u到頂點v的路徑但不是G中從u到v的最寬路徑，而路徑P*(u,v)才是最寬路徑。我們證明這會導致矛盾。假設邊(x,y)和邊(x*,y*)分別是P(u,v)和P*(u,v)的瓶頸。那么，必有關系w(x,y)<w(x*,y*)≤P*(u,v)上任一條邊的權。如下圖所示，如果我們把邊(x,y)從T中刪除，T便分裂為兩個不相交子樹T1和T2，并且假設x和u屬於T1而y和v屬於T2。那么，路徑P*(u,v)必定經過一條連接T1和T2的邊(a,b)。那么，T’=T1T2{(a,b)}便是一個支撐樹并有權值W(T’)=W(T1)+W(T2)+w(a,b)=W(T1)+W(T2)+w(x,y)+[w(a,b)-w(x,y)]=W(T)+[w(a,b)-w(x,y)]因為路徑P*(u,v)的寬度比P(u,v)寬，我們有w(x,y)<w(a,b)，從而有W(T’)=W(T)+[w(a,b)-w(x,y)]>W(T)，這與T是最大支撐樹矛盾。重新考慮第11題，不同的是，題中W不再是常數(shù)，而是一個任意的正整數(shù)。我們把題目重述如下。假設G=(V,E)是一個加權的連通圖并有|V|=n,|E|=m。又設每條邊e上的權為1到W之間的某個整數(shù)，1w(e)W，這里W是一個任意的正整數(shù)。修改Prim算法使得最小支撐樹可以在O(nW+m)時間內算出。*解釋如何設計一個O(mlgW)算法找到這個圖的最小支撐樹(不需詳細偽碼)。(提示：用紅黑樹。)解:(a) 算法與第11題的解相同。我們重寫在下面，但復雜度的分析不同。我們定義集合L[k]={u|d(u)=k}(0￡k￡W)和L[W+1]={u|d(u)=￥}。我們用鏈表把每個集合中頂點鏈接起來。一開始，L[0]={s}，L[W+1]=V–{s}，L[k]=，k?{1,2,…,W}。這些鏈表的總和組成Q。每當算法需要做Extract-Min(Q)時，我們就順序搜索L[0]，L[1]，L[2]，…，直到找到一個非空的鏈表L[k]。那么，這個鏈表中任一頂點v的d(v)值必定是k，并且是最小的。我們取出該鏈表中首項。這一步最多須要查W+2個鏈表，時間為O(W)。因總共需要做n次循環(huán)，這部分總時間為O(nW)。當一個頂點u的d(u)值需要從k更新到p<k時，我們只需把頂點u從鏈表L[k]摘下來，然后掛到鏈表L[p]上去即可。因此每一次更新只需O(1)時間。因為一共有O(m)個更新操作，所以算法的復雜度為O(nW+m)。下面是該算法偽碼。Modified-Prim’s-algorithm(G(V,E),s)foreachv?V d(v)?￥ p(v)?nil mark(v)Fendford(s)?0A? ConstructT(V,A)fork=1toW L[k]? //初始化鏈表，建立指向鏈表L[k]的指針，首項為空endforL[0]?{s}L[W+1]=V–{s}forj1ton i?0 whileL[i]=? i?i+1 endwhile u?ExtractheadfromL[i] //從L[i]中刪除首項 A?Aè{(p(u),u)} //加一條安全邊。u=s時，p(u)=nil，不操作 mark(u)T foreachv?Adj(u) ifmark(v)=Fandw(u,v)<d(v) //更新u的鄰居v then p(v)?u k?d(v) L[k]?L[k]-{v} //從L[k]中刪除點v d(v)?p?w(u,v) L[p]?L[p]è{v} //在L[k]尾部插入點v endif endforendforreturnT(V,A)End(b) 如果照上面(a)部分做法，為每一個權值k，建一個鏈表L[k](0￡k￡W+1)那么算法復雜度至少是(W)。因為W可以是任意大正數(shù)，這樣做不能滿足O(nlgW)要求。所以，我們的做法是，僅當權值k確實出現(xiàn)在某條邊上，才建鏈表L[k]。我們用紅黑樹（參見附錄A）作為數(shù)據(jù)結構。如果樹中有W個內結點，那么紅黑樹可以在O(lgW)時間內完成以下操作：尋找紅黑樹里是否有結點含有關鍵字x，RB-Search(T,x)插入一個關鍵字x，RB-Insert(T,x)刪除一個關鍵字x，RB-Delete(T,x)尋找紅黑樹里最小的關鍵字x，RB-min(T,x)初始時，我們建立兩個鏈表：L[0]?{s}L[]=V–{s}。這里L[k]表示是所有d(v)=k的頂點組成的鏈表。然后初始化紅黑樹T，使它含有兩個內結點，一個含有指向L[0]的指針，另一個含有指向L[]的指針。其它的初始化與上面(a)部分同。當我們需要Extract-min(Q)時，我們可如下操作：kRB-min(T,x)uheadofL[k] //鏈表L[k]首項對應頂點udeleteufromL[k] //把頂點u從L[k]刪除ifL[k]= thenRB-Delete(T,k) //這時，T(V,A)之外沒有d(v)=k的頂點endif當我們需要把頂點v的d(v)值，從d(v)=k更新為d(v)=p時，p<k，我們可如下操作：deletevfromL[k]ifL[k]= thenRB-Delete(T,k)endififRB-Search(T,p)=true //紅黑樹中有指向L[p]的指針，L[p]非空 then L[p]L[p]{v} //插入點v else L[p] //建立并初始化鏈表L[p] L[p]L[p]{v} //含一個頂點v RB-Insert(T,p) //紅黑樹中插入指向L[p]的指針endif由以上討論可見，紅黑樹里結點都指向不同的鏈表，所以內結點的個數(shù)最多是W，當然，也不會大于m。再有，每個操作，不論是Extract-min(Q)還是更新d(v)，都需要最多O(lgW)時間。因為總共有n個Extract-min(Q)操作和O(m)個更新操作，所以算法的復雜度為O(nlgW+mlgW)=O(mlgW)。如果加權連通圖G(V,E)的一個支撐子圖由k棵樹組成，則稱為k-樹支撐森林。一個支撐樹則是k=1時支撐森林的一個特殊情況。最小k-樹支撐森林是具有最小權值的一個k-樹支撐森林。證明下面計算最小2-樹支撐森林的算法正確Minimum-2-Tree-Spanning-Forest(G(V,E))用Kruskal或Prim算法計算G(V,E)的一個最小支撐樹T找出T中有最大權值的邊eFT–{e}returnFEnd請設計一個高時效的計算圖G(V,E)的最小k-樹支撐森林(k2)的算法并證明其正確性和分析其復雜度。解: (a)我們用反證法證明。假設T和F分別是上面算法得到的最小支撐樹和2-樹支撐森林，但F的權值不是最小的。設最小2-樹支撐森林是F*，它含有兩個樹T1和T2，并有W(F)>W(T1)+W(T2)。T1和T2對應了一個頂點的分割C={P,V-P}，其中P包含T1中的所有頂點，而V-P包含T2中的所有頂點。設E*為所有交叉邊的集合，即E*={(u,v)E|uT1，vT2}。那么，因T中有從T1中點到T2中點的路徑，E*必定含有一條T里的邊。假設邊(u,v)T并且(u,v)E*。那么，T*=T1T2{(u,v)}是G的一個支撐樹。因為w(u,v)w(e)，所以有W(T*)=W(T1)+W(T2)+w(u,v)<W(F)+w(e)=W(T)。這與T是最小支撐樹相矛盾。所以算法正確。(b)Minimum-k-Tree-Spanning-Forest(G(V,E)) //kn1 用Kruskal或Prim算法計算G(V,E)的一個最小支撐樹T2 找出T中(k-1)條有最大權值的邊e1,e2,…,ek-13 FT–{e1,e2,…,ek-1}4. ReturnF正確性證明：我們對k進行歸納證明。歸納基礎:問題(a)證明了k=2的情況。歸納步驟:假定對最小(k-1)-樹的支撐森林，k3，上面算法都能正確計算，我們證明上面算法也能正確算出最小k-樹的支撐森林。假設T和F分別是上面算法得到的最小支撐樹和k-樹支撐森林，但F的權值不是最小的。假設最小k-樹支撐森林是F*，它的k個樹為T1,T2,…,Tk。我們將證明W(F)W(T1)+W(T2)+…+W(Tk)=W(F*)。我們用E*表示子樹T1,T2,…,Tk之間的所有邊的集合，即E*={(u,v)E|uTi和vTj,1i,jk,ij}。那么，E*必定有(k-1)條在T里的邊。這是因為T1,T2,…,Tk把G的頂點分割為k個集合，所以至少要k-1條邊才可以把它們連結成一棵樹。所以|E*T|(k-1)。假定邊(u,v)是E*T中權值最小的邊。因為上面算法中刪去的是樹T中權值最大的(k-1)條邊，e1,e2,…,ek-1，且滿足w(e1)w(e2)…w(ek-1)，所以我們有w(u,v)w(ek-1)。因為F*{(u,v)}=T1T2…Tk{(u,v)}形成一個(k-1)-樹支撐森林，由歸納假沒，F(xiàn){ek-1}是一個最小(k-1)-樹支撐森林，所以有W(F{ek-1})W(F*{(u,v)})。也就是W(F)+w(ek-1)W(F*)+w(u,v)。所以有：W(F)W(F*)+w(u,v)-w(ek-1)。因為w(u,v)w(ek-1)，所以有W(F)W(F*)。證畢。算法第二步從n個數(shù)中找k個最大的數(shù)可以用第5.4.3節(jié)的方法在O(n+klgn)=O(nlgn)時間內完成，因此，算法復雜度與計算最小支撐樹相同。加權連通圖G(V,E)的一個支撐樹的瓶頸邊是這棵樹中有最大權值的一條邊，其權值稱為這個樹的瓶頸值。如果一個支撐樹的瓶頸值是G的所有支撐樹中最小的，那么這個支撐樹稱為瓶頸支撐樹，記為BT(G)。證明最小支撐樹也是一個瓶頸支撐樹。設計一個線性時間的算法以決定給定的加權連通圖G(V,E)是否有瓶頸值不大于b的支撐樹。*解釋如何設計一個線性時間的算法找出加權連通圖G(V,E)的瓶頸支撐樹。不要求偽碼。解:證明：我們用BN(T)表示樹T的瓶頸值。假設T是圖G(V,E)的最小支撐樹，而BT是G的瓶頸支撐樹。假設T和BT的瓶頸邊分別是(u,v)和(a,b)，我們要證明w(u,v)w(a,b)，即BN(T)BN(BT)。為了用反證法證明，我們假定w(u,v)>w(a,b)，并證明導致矛盾。我們把邊(u,v)從T中刪去后，T分裂為不相交的兩個子樹T1和T2，uT1，vT2。讓U表示在T1中頂點的集合，V-U表示在T2中頂點的集合，那么C=(U，V-U)是V的一個割(見下圖)。UUV-UuvxyT1T2因為w(u,v)>w(a,b)，邊(u,v)BT。那么，如果我們沿著BT中從頂點u到頂點v的路徑走，一定會碰到一條邊(x,y)，其中xU，yV-U。把邊(x,y)加到T1和T2中，我們得到一個支撐樹T*，T*=T1T2{(x,y)}=T{(x,y)}–{(u,v)}。它的權值是W(T*)=W(T)+w(x,y)–w(u,v)。 因為在BT中，邊(a,b)的權最大，而反證假設w(u,v)>w(a,b)，所以有w(u,v)>w(a,b)w(x,y)。因此有W(T*)=W(T)+w(x,y)–w(u,v)<W(T)。這與T是最小支撐樹相矛盾。設計一個線性時間的算法以決定給定的加權連通圖G(V,E)是否有瓶頸值不大于b的支撐樹。算法如下，其正確性一目了然。Exist-BT(G(V,E),b)foreachedgeeE ifw(e)>b thenEE–{e} endifendforSelectavertexsinVBFS(G(V,E),s) //從點s開始作廣度優(yōu)先搜索，產生BFS樹foreachvV ifcolor(v)=White thenreturn(nospanningtreeTwithBN(T)b) endifendforBTBFStreereturnBTEnd因為只需一輪BFS，算法的時間復雜度為O(m)。*解釋如何設計一個線性時間的算法找出加權連通圖G(V,E)的瓶頸支撐樹。不要求偽碼。算法的思路是用二元搜索找出最小瓶頸支撐樹T的BN(T)值。遞歸算法如下：BN(G(V,E))如果E中所有邊有相同權值b，停止并報告BN(G(V,E))=b。(遞歸見底)找出E中邊的權值的中位數(shù)。假設邊e的權值為中位數(shù)，w(e)=b。E1E中權值小于b的邊。E2E中權值等于b的邊。E3E中權值大于b的邊。如果圖G(V,E1)有BFS樹，則G(V,E)G(V,E1)。否則，如果圖G(V,E1E2)有BFS樹，則停止并報告BN(G(V,E))=b。否則，如下操作：設圖G(V,E1E2)有BFS森林，含有k個樹，T1,T2,…,Tk，也稱為分支。(8.1) 為每個G中頂點u打上分支號，分支(u)。(8.2) 構造分支圖中的點集合，V’={1,2,…,k}，頂點i(1ik)代表分支i。(8.3) 構造分支圖中的邊，E’={(分支(u),分支(v))|分支(u)分支(v)，(u,v)E3}。(8.4) V’中兩點間可能有多條邊，只保留一條有最小權值的邊。辦法是把所有E’中邊排序使得(i,j)<(u,v)如果i<u或者i=u但是j<v。顯然用計數(shù)排序O(n)=O(m)可完成。這樣一來，兩點間的多條邊在序列中就連在一起了，掃描這一序列一遍就可為兩點間保留一條有最小權值的邊。(8.5) G(V’,E’)是分支圖。G(V,E)G(V’,E’)。遞歸調用BN(G(V,E))。因為|E1|<m/2，|E3|<m/2，我們有遞推關系：T(m)<T(m/2)+cm。所以，該算法的復雜度是T(m)=(m)。找出最小瓶頸支撐樹T的BN(T)值以后，只需一次BFS搜索就可以找出最小瓶頸支撐樹T。假設連通圖G的邊可以是任意的權值，可正可負。請設計一個找最小支撐連通子圖的算法，使其復雜度與最小支撐樹一樣。請證明算法的正確性。注意，最小支撐連通子圖可能比最小支撐樹的邊多卻有更小的總權值。下圖給出了一個例子。aabcd-2-1-346有正負權值的連通圖Gabcd-2-34G的最小支撐樹abcd-2-34G的最小支撐連通子圖-1解： Minimum-Spanning-Connected-Subgraph(G(V,E))SelectavertexsVT(V,A)MST-Prim(G(V,E),s) //先算出一個MSTA’AforeachedgeeE ifw(e)<0andeA’ then A’A’{e} //把所有負值邊全包進來 endifendforreturnT’(V,A’) //T’(V,A’)是把所有負值邊全包進來后的圖End正確性證明：我們用反證法證明。假設最小支撐連通子圖G’(V,E’)的權值比T’(V,A’)小，W(G’)<W(T’)。顯然，G’必定含有所有負權值的邊，否則不會最小。我們把所有T’(V,A’)的邊分為3個集合：S1: 算法第2步中得到的最小支撐樹T(V,A)中有正權值的邊的集合。因為W(G’)<W(T’)，S1非空。S2: 算法第2步中得到的最小支撐樹T(V,A)中有負權值的邊的集合。由頂點V和S2中邊形成的子圖G(V,S2)必不連通，否則第2步中得到的最小支撐樹T(V,A)必不含有正權值的邊，與S1非空矛盾。因此S2中邊形成若干個連通分支，C1,C2,…,Ck(k>1)，并且每個分支是一棵樹。S3: 算法第3步以后加入A’中的邊的集合。我們斷言，任一條S3中的邊一定在上述某個分支內，而不會連接兩個分支，否則可找到有比T(V,A)更小權值的支撐樹而矛盾。顯然G’中邊也包含S2和S3，因為它要包含所有負權值的邊。S2S3是所有負權值的邊的集合。因此，G’中邊包含連通分支，C1,C2,…,Ck。我們把S3從G’中刪去，得到圖G’’=(V,E’-S3)。那么，我們斷言G’’必定是個連通圖，這是因為任一條S3中的邊一定在某個分支內，而不會連接兩個分支，所以刪除S3中的邊不會改變G’的連通性，所以圖G’’是連通的。因此G’’有最小支撐樹T’’并且T’’必定包含S2中所有邊。這是因為S2中所有邊不形成回路。因為T’’包含了G’’中所有負權值的邊，和一部分正權值的邊，所以有W(T’’)≤W(G’’)。因為T(V,A)是G的最小支撐樹，G’’G，我們有：W(T(V,A))≤W(T’’)≤W(G’’)，因此有W(T’(V,A’))=W(T(V,A))+W(S3)≤W(G’’)+W(S3)=W(G’)，與假設矛盾。無向連通圖的一棵支撐樹再加上一條邊稱為一棵1-樹。下面圖顯示了一個1-樹的例子。(a)(a)一個無向圖G(b)G的一棵1-樹abcdebcdea一個加權的無向連通圖G(V,E)的一棵1-樹稱為最小1-樹，如果它有最小的總權值。請設計一個復雜度好的計算最小1-樹的算法。你需要證明其正確性和分析復雜度。解： Minimum-1-Tree(G(V,E)) SelectavertexsVT(V,A)MST-Prim(G(V,E),s) //用Prim算法找出一個最小支撐樹TE’E–A //不在T里的剩余的邊集合ifE’= thenreturn(no1-treeexists) //1-樹不存在 else findeE’suchthatw(e)=min{w(e)|eE’} //E’中最小邊e returnT{e}endifEnd這個算法顯然有與Prim算法相同的復雜度。正確性證明：首先，如果集合E’是空集，那么1-樹不可能存在。所以假定E’。我們證明算法產生的T{e}必定是最小1-樹。假設T’{e’}是任意一個1-樹。因為T’{e’}含有一個回路C，那么C上必有一條邊e’’不屬於A而屬于E’。把這條邊從這個1-樹中刪去后得到一個支撐樹T’’，并且有權值為w(T’’)=w(T’)+w(e’)-w(e’’)。顯然也有w(T’)+w(e’)=w(T’’)+w(e’’)。那么，我們有如下關系：w(e’’)w(e) 因為e’’E’=E–A。w(T’’)w(T) 因為T和T’’都是G的支撐樹,但T是最小支撐樹。所以，我們有w(T’)+w(e’)=w(T’’)+w(e’’)w(T)+w(e)。這也就是說，任一棵1-樹的權值都大于等于算法產生的1-樹的權值，所以算法正確。假設T是圖G(V,E)的一棵以頂點s為根的最小支撐樹。如果我們把圖G(V,E)中的一條邊(u,v)的權值增加到w(u,v)，而這條邊也是T中的一條邊，(u,v)T，那么T就不一定是這個變化后的圖G(V,E)的一棵最小支撐樹了。請設計一個O(m)的算法把T修改為變化后的圖G(V,E)的一個最小支撐樹并證明其正確性。解: 我們的做法是，把邊(u,v)從樹T里刪去，得到兩個子樹，T1和T2。T1和T2形成對頂點集合V的分割,C=(U1，U2)，其中U1包含T1中所有頂點，U2包含T2中所有頂點。然后，在圖G里找出這個割的最小交叉邊e，那么T1T2{e}形成的樹就是答案。Modify-MST-Increase-Weight(G(V,E),T,u,v)foreachvV Adj(v) //為樹T的每個頂點建鄰居集合，初始為空endfor foreachvV if(v)=w //(w,v)是一條邊 then Adj(w)Adj(w){v} //w和v互為鄰居 Adj(v)Adj(v){w} endifendforTT–{(u,v)} //刪除邊(u,v)后，T=T1T2。設uT1,vT2BFS(T,u)andcolorallvisitedverticesred //只能訪問到T1中點，并著為紅色BFS(T,v)andcolorallvisitedverticesblue//只能訪問到T2中點，并著為藍色e(u,v)ww(u,v)foreachedge(x,y)E //找最小交叉邊 if(color(x)≠color(y))andw(x,y)<w then e(x,y) ww(x,y) endifendforT’T{e} //也就是T1T2{e}returnT’End正確性證明：設T*是邊(u,v)的權值增加后的圖G(V,E)的任意一個支撐樹。我們證明W(T’)W(T*)，這里，T’是我們算法產生的支撐樹。我們分兩種情況證明.T*包含邊(u,v)。如果是這種情況，我們把邊(u,v)從T*中刪去后得到子樹T1*和T1*。因為T是圖G的一棵最小支撐樹，所以有W(T1)+W(T2)+w0(u,v)W(T1*)+W(T2*)+w0(u,v)。這里，w0(u,v)是邊(u,v)原來的權值。所以有W(T1)+W(T2)W(T1*)+W(T2*)。因為w(e)w(u,v)，這里e是算法得到的割C=(U1，U2)的最小交叉邊，其中，U1包含T1中所有頂點，U2包含T2中所有頂點。所以有：W(T1)+W(T2)+w(e)W(T1*)+W(T2*)+w(u,v)，也就是W(T’)W(T*)。T*不包含邊(u,v)。如果是這種情況，在T*中，從點u到點v的路徑上，一定有一條邊(x,y)與割C=(U1，U2)相交。因為邊(u,v)是原圖中這個割的最小交叉邊，w0(u,v)w(x,y)，這里，w0(u,v)是邊(u,v)原來的權值?，F(xiàn)在，如果把邊(x,y)從T*中刪去，則會得到子樹T1*和T2*，使得點u和點v分屬兩邊。因為，T1*T2*{(u,v)}也是原圖G的一棵支撐樹，而T是一棵最小支撐樹，故有：W(T1)+W(T2)+w0(u,v)W(T1*)+W(T2*)+w0(u,v)。所以有：W(T1)+W(T2)W(T1*)+W(T2*)。因為邊e是(u,v)的權值增加后的圖G中割C=(U1，U2)的最小交叉邊，所以有w(e)w(x,y)。因此有W(T1)+W(T2)+w(e)W(T1*)+W(T2*)+w(x,y)。這就證明了W(T’)W(T*)。因為T有n個點，n-1條邊，算法在第14行前只需O(n)時間，而第15行的循環(huán)有O(m)的復雜度，所以算法有O(m)的復雜度。假設T是圖G(V,E)的一棵最小支撐樹。它的邊是e1,e2,…,en-1，并有權值順序為w1w2…wn-1，這里，n=|V|。我們定義T的一個子圖Ti(V,Ei)如下。子圖Ti(V,Ei)有與T相同的頂點集合V，但它的邊是Ei=e1e2…ei，即它的邊是由T中權值最小的i條邊組成(0in-1)。當i=0時，T0不含有邊，只含n個頂點。顯然，Ti由n-i個連通分支組成，C1,C2,…,Cn-i，而每個連通分支是一棵T的子樹。證明圖G(V,E)里，除Ei以外的任一條邊e，eE-Ei，如果它連結分屬兩個不同分支的兩個點，那么，它的權值w(e)大于等于wi+1，即w(e)wi+1。證明：為了用反證法，假設有邊e=E-Ei，連結C1和C2，但w(e)<wi+1。設e=(a,b)，其中aC1，bC2。因為eEi而且w(e)<wi+1，邊e不可能屬于T，e{e1,e2,…,en-1}。考慮T中從點a到點b的路徑P(a,b)。它必定經過T-Ei中某條邊e*，即e*{ei+1,ei+2,…,en-1}。我們有：w(e)<wi+1w(e*)。如果我們把e*從T中刪去，把邊e加進來，我們會得到一個權值更小的支撐樹T’:W(T’)=W(T)-w(e*)+w(e)<W(T)。這與T是最小支撐樹矛盾。*假設T是圖G(V,E)的一個最小支撐樹。它的邊是e1,e2,…,en-1，并有權值順序為w1w2…wn-1，這里，n=|V|。假設T’是圖G的另一個支撐樹，它的邊是e’1,e’2,…,e’n-1，并有權值順序為w’1w’2…w’n-1。證明wiw’i(1in-1)。(題示：先做第19題。)解：我們對i用歸納法證明。 歸納基礎。當i=1時，由19題知，w1w’1。 歸納步驟。假設我們有w1w’1,w2w’2,…,wkw’k(k1)，我們證明必有wk+1w’k+1。我們用反證法。假設有wk+1>w’k+1。我們定義子圖Tk(V,Ek)，它的頂點集合V與G相同，邊集合是Ek=e1e2…ek，即它的邊是由T中權值最小的k條邊組成(0kn-1)。當k=0時，T0不含有邊，只含n個頂點。顯然，Tk有n-k個連通分支，C1,C2,…,Cn-k，每一分支是一棵樹。由19題知，任何集合E–Ek中的邊e，如果連結不同分支的話，必有w(e)wk+1。因為w’k+1<wk+1，所以邊e’k+1必定連結同一分支的兩個點。又因為w’1w’2…w’k+1，所以邊e’1,e’2,…,e’k也必定是連結同一分支中的點。所以這n-k個分支含有集合S’={e’1,e’2,…,e’k+1}中所有k+1條邊。讓我們假設這n-k個分支中頂點的個數(shù)分別是n1,n2,…,nn-k。因為T’是圖G的一個支撐樹，不含回路，所以這n-k個分支中能夠含有T’中邊的個數(shù)必定小于等于(n1-1)+(n2-1)+…+(nn-k-1)=n1+n2+…+nn-k–(n–k)=n–(n–k)=k。這就產生了矛盾。所以，必定有wk+1w’k+1，歸納成功。假設T是圖G(V,E)的一個最小支撐樹。設圖中的一條邊(u,v)E不屬于T，(u,v)T。請設計一個O(n)的算法去修改一下T使得修改后的支撐樹含邊(u,v)并且有最小權值。你需要證明它的正確性。解：偽碼如下，證明隨后。Modify-MST(T,u,v)BFS(T,u)andgetaBFStree //從頂點u開始對T作BFS，并得到BFS樹w-bv //從頂點v開始，沿著到頂點u的路徑，找權值最大邊a(v)whileanil ifw(a,b)>w then ww(a,b) xa yb endif ba a(a)endwhileT’(T–{(x,y)}){(u,v)}returnT’End正確性證明：假設T*是含有邊(u,v)的一棵支撐樹，我們證明有W(T’)W(T*)，這里T’是上面算法產生的支撐樹。如果我們把邊(u,v)從T*刪去，那么如下圖(a)所示，得到兩個子樹，T1*和T2*，頂點u屬于T1*，頂點v屬于T2*。如果我們沿著最小支撐樹T中從頂點u到頂點v的路徑走，那么，如圖(b)所示，一定會碰到一條邊(a,b)，其中，aT1*和bT2*。把邊(a,b)從最小支撐樹T中刪除會得到T的兩個子樹，T1和T2。因為邊(a,b)連接T1*和T2*，那么T1*T2*{(a,b)}是一個支撐樹。因為T是最小支撐樹，所以有W(T1)+W(T2)+w(a,b)W(T1*)+W(T2*)+w(a,b)。從而有：W(T1)+W(T2)W(T1*)+W(T2*)。因此有：W(T1)+W(T2)+w(u,v)W(T1*)+W(T2*)+w(u,v)=W(T*)。因為，由算法知：W(T’)=W(T)-w(x,y)+w(u,v)=[W(T1)+W(T2)+w(a,b)]-w(x,y)+w(u,v)=W(T1)+W(T2)+w(u,v)+(w(a,b)-w(x,y))W(T1)+W(T2)+w(u,v) //因為由算法知w(a,b)w(x,y)所以有W(T’)W(T*)。這證明了算法的正確性，其復雜度顯然是O(n)。假設T是圖G(V,E)的一個最小支撐樹。我們考慮如何能在O(n2)時間里找到第二小的支撐樹。第二小的支撐樹指的是所有與T不同的支撐樹中權值最小的一個。我們假設G(V,E)T，否則不存在。我們分三個小問題來解決。假設我們的算法需要對一個堆棧S作一系列的Push(S,x)和Pop(S)的操作，其中Push(S,x)表示把數(shù)字x壓入堆棧S，Pop(S)表示把棧頂?shù)脑貜棾觥４送?，我們的算法需要能夠知道當前堆棧S中哪個元素最大，它的數(shù)字是多少。請設計一個簡單算法，任憑堆棧S如何動態(tài)變化，都能在O(1)時間里幫我們找到當前堆棧中這個最大元素。假設T(V,E,r)是一個以頂點r為根的樹，樹中的每條邊有實數(shù)權值。我們用M(r,v)表示在從根r到頂點v的路徑上的邊的最大權值。下圖給出了一個例子。rr57-3-6abcdfghiljke9-428910611M(r,a)=5,M(r,b)=9,M(r,c)=5,M(r,d)=5,M(r,e)=11,M(r,f)=-3,M(r,g)=-3,M(r,h)=9,M(r,i)=8,M(r,j)=10,M(r,k)=8,M(r,l)=7.請設計一個O(n)的算法為樹中每一個根以外的頂點vV，v≠r，計算M(r,v)，這里n=|V|。我們假定，每個頂點u的父親已知，是π(u)，根的父親是π(r)=nil。另外，每個頂點u的兒子們由一個鏈表組織起來，用“vu’snextson”語句就可以訪問頂點u的下一個兒子或第一個兒子。如果u’snextson=nil，則表明頂點u的所有兒子們都已被算法訪問過了，或者頂點u是個樹葉。請設計一個O(n2)算法為加權連通圖G(V,E)找出第二小的支撐樹。為簡單起見，我們假定圖G的所有邊的權值都不同，并已知T是圖G(V,E)的MST。解: (a) 我們用另外一個堆棧S’來幫忙，使得S’的頂始終指向堆棧S中的最大數(shù)。我們假定一開始時，堆棧S和S’都是空的。每當我們操作Push(S,x)或Pop(S)時，我們對堆棧S’作出相應的更新操作。具體做法如下：(1)每次Push(S,x)以后，進行以下操作：ifS’=orxTop(S’) //否則不操作 thenPush(S’,x) //x是堆棧S中最大的數(shù)(2)每次Pop(S)以前，進行以下操作： ifS’andTop(S)=Top(S’) //否則不操作 thenPop(S’)正確性證明：我們用歸納法證明，如果堆棧S非空，Top(S’)始終指向堆棧S中的最大數(shù)。歸納基礎：一開始時，堆棧S和S’都是空的。命題正確。當?shù)谝粋€數(shù)壓入堆棧S時，這個數(shù)也被壓入堆棧S’，命題正確。歸納步驟：