計(jì)算機(jī)算法基礎(chǔ) 第2版 習(xí)題及答案 第8章

PAGE23第8章 圖的周游算法假設(shè)T是一個(gè)邊上加了權(quán)的有n個(gè)頂點(diǎn)的樹，而頂點(diǎn)x是其中一個(gè)指定的頂點(diǎn)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)復(fù)雜度為O(n)的算法，取名Distance(T,x)，算出從頂點(diǎn)x到其他每一個(gè)頂點(diǎn)v的距離d(x,v)。這里，邊是無(wú)向的，兩點(diǎn)間的距離是指這兩點(diǎn)間一條簡(jiǎn)單路徑可能有的最小的邊的總權(quán)值。解：用BFS或者DFS都可以解。下面是用BFS來(lái)解。做法是，我們從頂點(diǎn)x出發(fā)進(jìn)行BFS搜索。在初始化時(shí)，給每個(gè)頂點(diǎn)v置d(x,v)=，但置d(x,x)=0。在這個(gè)過(guò)程中，每當(dāng)我們從頂點(diǎn)u訪問(wèn)它的一個(gè)兒子v時(shí)，則更新d(x,v)=d(x,u)+w(u,v)，其中w(u,v)是邊(u,v)上的權(quán)。因?yàn)闃銽中邊的個(gè)數(shù)m=n-1，所以算法有復(fù)雜度是O(n)。正確性顯然。Distance(T,x)foreachvT color(v)=White d(x,v) (v)nil //表示父親指針為空endford(x,x)0Q //先把隊(duì)列清空Enqueue(Q,s) //將s進(jìn)隊(duì)，初始化完成whileQ uDequeue(Q) //取出隊(duì)列首項(xiàng) foreachvAdj(u) ifcolor(v)=White then color(v)Gray d(x,v)d(x,u)+w(u,v) (v)u Enqueue(Q,v) endif endforendwhileEnd假定T=(V,E)是一棵有n個(gè)頂點(diǎn)的樹，它的每條邊(u,v)是無(wú)向的，并有正數(shù)權(quán)值w(u,v)>0。它的直徑定義為T中最長(zhǎng)的一條路徑的長(zhǎng)度,即Diameter(T)=maxu,v∈∈Vδ(u,v)，這里d(u,v)表示點(diǎn)u和點(diǎn)v之間距離，也就是點(diǎn)u和點(diǎn)v之間一條簡(jiǎn)單路徑可能有的最小的邊的總權(quán)值。證明下面的算法在O(n)時(shí)間里正確算出Diameter(T)。算法中所用函數(shù)Distance(T,x)Diameter(T)SelectanodexinT //任選一點(diǎn)xDistance(T,x) //調(diào)用第1題的算法為T中每一點(diǎn)v計(jì)算d(x,v)Findnodevsuchthatd(x,v)isthelargest //找出與點(diǎn)x距離最大的點(diǎn)vDistance(T,v) //再調(diào)用第1題的算法為T中每一點(diǎn)u計(jì)算d(v,u)Findnodeusuchthatd(v,u)isthelargest //找出與點(diǎn)v距離最大的點(diǎn)uReturnDiameter(T)=d(v,u) //d(v,u)就是直徑End證明：首先，這個(gè)算法的復(fù)雜度是O(n)，因?yàn)槊恳徊降膹?fù)雜度為O(n)。我們只需證明其正確性。為了用反證法來(lái)證明，我們假設(shè)樹的直徑是d(a,b)并且d(a,b)>d(v,u)。因?yàn)樗袡?quán)值為正數(shù)，所以a和b必定是樹的葉子。如果a=x，(上面算法第1步)那么，因?yàn)閐(x,v)是所有到x的距離中最大的，我們有d(a,b)=d(x,b)≤d(x,v)≤d(u,v)，產(chǎn)生矛盾。我們可假定a≠x。同理可推出a≠v，b≠x，b≠v。(它們也許等于u)?，F(xiàn)在來(lái)看一下算法中第一次調(diào)用距離算法得到的BFS樹，其頂點(diǎn)x是根。從x到各點(diǎn)的路徑中，以d(x,v)最長(zhǎng)。設(shè)葉子a和b的最小公共祖先是頂點(diǎn)w，也就是從a到x的路徑與從b到x的路徑第一個(gè)相交的點(diǎn)。又設(shè)k為葉子a和葉子v的最小公共祖先(見(jiàn)下圖)。xxkbvwa(a)情況1:頂點(diǎn)k是頂點(diǎn)w的祖先或與點(diǎn)w重合xwvbka(b)情況2:頂點(diǎn)w是頂點(diǎn)k的祖先我們分兩種情況討論：頂點(diǎn)k是頂點(diǎn)w的祖先或與點(diǎn)w重合。即d(x,k)d(x,w)。圖(a)顯示了這種情況。在這種情況下，我們有d(b,w)≤d(b,k)≤d(v,k)。所以，我們有以下推導(dǎo):d(a,b)=d(a,w)+d(b,w)=d(a,w)+d(b,k)-d(w,k)d(a,w)+d(v,k)-d(w,k)=d(a,k)-d(w,k)+d(v,k)-d(w,k)=d(a,k)+d(v,k)-2d(w,k)=d(a,v)-2d(w,k)≤d(a,v)≤d(u,v)。這與d(a,b)>d(v,u)矛盾。頂點(diǎn)w是頂點(diǎn)k的祖先。即d(x,w)d(x,k)。圖(b)顯示了這種情況。在這種情況下，我們有d(a,k)≤d(v,k)。所以有以下推導(dǎo)：d(a,b)=d(a,k)+d(k,w)+d(b,w)d(v,k)+d(k,w)+d(b,w)=d(v,w)+d(b,w)=d(v,b)≤d(v,u)這也與d(a,b)>d(v,u)矛盾。所以d(v,u)是直徑。當(dāng)我們用鄰接矩陣來(lái)表示有n個(gè)頂點(diǎn)的圖時(shí)，大多數(shù)圖的算法需要(n2)時(shí)間，但是也有特例。請(qǐng)考慮下面的問(wèn)題。一個(gè)簡(jiǎn)單有向圖的一個(gè)頂點(diǎn)稱為是總匯點(diǎn)(universalsink)，如果每一個(gè)其他頂點(diǎn)都有一條邊指向這個(gè)頂點(diǎn)，而它卻沒(méi)有出去的邊。也就是說(shuō)，如果一個(gè)頂點(diǎn)的入度是n-1而出度為0，那么這個(gè)點(diǎn)稱為總匯點(diǎn)。假設(shè)我們用鄰接矩陣來(lái)表示一個(gè)簡(jiǎn)單有向圖。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)的算法來(lái)判斷這個(gè)圖是否有總匯點(diǎn)，如果有則輸出這個(gè)點(diǎn)。解：設(shè)A為鄰接矩陣，頂點(diǎn)標(biāo)號(hào)為1到n。簡(jiǎn)單有向圖有A[i,i]=0(1in)，即對(duì)角線元素為0。頂點(diǎn)i是總匯點(diǎn)的充要條件是:對(duì)每一個(gè)j(1jn)，都有A[i,j]=0，對(duì)每一個(gè)k(1kn,ki)，都有A[k,i]=1。這也就是說(shuō)，第i行的元素都是0。而第i列的元素，除A(i,i)以外，都是1。顯然總匯點(diǎn)如果存存，它是唯一的。下面是這題的算法。Universal-Sink(A[1..n,1..n])//A是鄰接矩陣且A[i,i]=0(1in)。i1j1whileinandjn ifA[i,j]=0 //檢查第i個(gè)點(diǎn)的可能性，如A[i,j]=1，則查i+1 then jj+1 else ii+1 endifendwhileifi>n thenreturn(nouniversalsink) elseif(A[i,k]=0foranyk,1kn)and(A[k,i]=1foranyk,ki,1kn) thenreturn(vertexiistheuniversalsink) elsereturn(nouniversalsink) endifendifEnd算法的復(fù)雜度顯然是O(n)因?yàn)樵趙hile循環(huán)中，指針i和j都只能最多增加n次，而第11行的驗(yàn)證也只需O(n)時(shí)間。它的正確性證明如下：While循環(huán)的目的是找到一個(gè)頂點(diǎn)，它有可能成為總匯點(diǎn)。我們從A[1,1]開始一行一行看。如果在這行中有一個(gè)1，那么查下一行。在查下一行時(shí)，我們不需從頭查起，只需從當(dāng)前列查起。下面的圖解釋了這個(gè)循環(huán)的做法。如下圖所示，循環(huán)的結(jié)果有兩種，i>n和i≤n。0000…0111…100…0111…100…00(b)第二種情況：in第i行00…0111…100…0111…100…01(a)第一種情況：i>n11…1第i行如果是第一種情況，i>n，那么不可能存在總匯點(diǎn)，這是因?yàn)槊恳恍兄卸加幸辉貫?。如果是第二種情況，那么頂點(diǎn)i是唯一的可能。這是因?yàn)閷?duì)應(yīng)頂點(diǎn)1，2，…，(i-1)的行都有一個(gè)元素為1，又因?yàn)闃?biāo)號(hào)大于i的每一個(gè)列中都有一個(gè)0出現(xiàn)在第i行之前或出現(xiàn)在第i行之中。因此，我們只需查驗(yàn)頂點(diǎn)i即可。算法第11行完成這一查驗(yàn)工作。用DFS設(shè)計(jì)一個(gè)O(m+n)算法來(lái)判定一個(gè)無(wú)向圖是否含有一個(gè)奇回路，即有奇數(shù)條邊的回路。解：我們知道一個(gè)無(wú)向圖沒(méi)有奇回路的充要條件是可以二著色。所以用書中BFS的二著色算法來(lái)做是可以的。這里，題目要求用DFS判斷，其做法類似。我們?cè)谶M(jìn)行DFS時(shí)給頂點(diǎn)用紅、藍(lán)著色。先把根著為紅色。以后每訪問(wèn)一個(gè)新的頂點(diǎn)，就把這點(diǎn)著為與它父親顏色相反的顏色。當(dāng)我們發(fā)現(xiàn)一條反向邊時(shí)，則檢查這條邊的兩端是否同色。如果是，則發(fā)現(xiàn)一個(gè)奇回路。算法包括主程序和子程序。偽碼如下，正確性顯然。Odd-Cycle(G(V,E)) //主程序foreachuV color(u)White (u)nilEndforfoundfalse //Noodd-cyclehasbeenfoundforeachuV ifcolor(u)=White then Odd-Cycle-Check(u) iffound=true thenreturn(Thereisanoddcycle) endif endifendforreturn(Graphhasnooddcycles)EndOdd-Cycle-Check(s)Color(s)RedS //清空堆棧Push(S,s)whileS uTop(S) //不是彈出，而是建立指針 vu’snextneighborinAdj(u) //u的鄰接表中下一個(gè)鄰居v ifv=nil //u的鄰居已全部訪問(wèn)完畢 then Pop(S) //u由棧頂彈出 else ifcolor(v)=White //u的下一個(gè)鄰居是白色 then color(v)not(color(u))//著相反顏色 Push(S,v) else ifcolor(v)=color(u) then foundtrue return endif endif endifendwhileEnd*重做第2題，但是這次我們?cè)试ST=(V,E)的每條邊(u,v)的權(quán)值可以是任何實(shí)數(shù)。它的直徑仍然定義為圖中最長(zhǎng)的一條簡(jiǎn)單路徑的加權(quán)長(zhǎng)度,即Diameter(T)=maxu,v∈∈Vδ(u,v)(可能是負(fù)數(shù))。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)時(shí)間的算法算出Diameter(T)。為方便起見(jiàn)，我們假定T是一個(gè)根樹，頂點(diǎn)s是根。另外，每個(gè)內(nèi)結(jié)點(diǎn)u有個(gè)兒子的集合Son(u)，類似于Adj(u)。如果Son(u)=，則表明頂點(diǎn)解：我們注意到，如果d(u,v)是直徑，那么有兩種情況：頂點(diǎn)u是頂點(diǎn)v的祖先，或頂點(diǎn)v是頂點(diǎn)u的祖先。頂點(diǎn)u和頂點(diǎn)v沒(méi)有直系親屬關(guān)系，從點(diǎn)u到點(diǎn)v的路徑通過(guò)它們的最小公共祖先，點(diǎn)w。不論哪種情況，我們從根s起，對(duì)樹T=(V,E)作DFS。在DFS進(jìn)行時(shí)，我們?cè)诿總€(gè)內(nèi)結(jié)點(diǎn)u計(jì)算以下兩個(gè)值。從點(diǎn)u到它的子孫中最長(zhǎng)的一條路徑d1(u)=(u,u1)。其中，點(diǎn)u1屬于點(diǎn)u為根的子樹。從點(diǎn)u到它的子孫中第2長(zhǎng)的一條路徑d2(u)=(u,u2)。其中，點(diǎn)u2屬于點(diǎn)u為根的子樹。當(dāng)點(diǎn)u回溯到父親(u)時(shí)，如果d2(u)>0，那么d1(u)+d2(u)就是點(diǎn)u為根的子樹中經(jīng)過(guò)點(diǎn)u的最長(zhǎng)路徑，否則，d1(u)就是點(diǎn)u為根的子樹中以點(diǎn)u為起點(diǎn)的最長(zhǎng)路徑。所有這些路徑中最長(zhǎng)的路徑就是本題的解。我們可用一個(gè)全局變量(i,j)來(lái)記錄目前最好的解。下面是偽碼，正確性顯然。Diameter(T,s,i,j,) //(i,j)是直徑- //初始化ijnilS //清空堆棧Push(S,s)whileSuTop(S) //不是彈出，而是建立指針 vu’snextsoninSon(u) //u的兒子表中下一個(gè)兒子v ifv=nil //u的兒子已全部訪問(wèn)完畢 then Pop(S) //u由棧頂彈出 ifd2(u)>0 //點(diǎn)u為根的子樹中經(jīng)過(guò)u的最長(zhǎng)路徑 then ifd1(u)+d2(u)> //點(diǎn)u的子樹中經(jīng)過(guò)u的最長(zhǎng)路徑 then d1(u)+d2(u) iu1 ju2 endif else ifd1(u)> //點(diǎn)u的子樹中從u開始的最長(zhǎng)路徑 then d1(u) iu ju1 endif endif if(u)=znil //更新父親的d1和d2 thenifd1(u)>0 then ifw(z,u)+d1(u)>d1(z) thend1(z)w(z,u)+d1(u) z1u1 elseifw(z,u)+d1(u)>d2(z) thend2(z)w(z,u)+d1(u) z2u1 endif endif else ifw(z,u)>d1(z) thend1(z)w(z,u) z1u else ifw(z,u)>d2(z) thend2(z)w(z,u) z2u endif endif endif endif else //點(diǎn)v還沒(méi)有被訪問(wèn) Push(S,v) d1(v) d2(v)- (v)u endifendwhilereturn,i,jEnd假設(shè)一個(gè)連通的無(wú)向圖G(V,E)的邊只有兩種權(quán)值，w(>0)或者2w。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(m+n)的算法計(jì)算從頂點(diǎn)u到頂點(diǎn)v的最短路徑。解: 解題思路是，第1步，我們先在每一個(gè)有2w權(quán)值的邊上加上一個(gè)點(diǎn)，也就是把這條邊一分為二，并且給每條邊賦以權(quán)值w。這樣一來(lái)，圖中每條邊的權(quán)值都相等。第2步，我們用廣度優(yōu)先搜索在這個(gè)修改后的圖G’里找到頂點(diǎn)u到頂點(diǎn)v最短路徑。最后，第3步，我們把在第1步中加的點(diǎn)從這條路徑上去掉。偽碼如下。Shortest-Path(G(V,E),u,v)G(V’,E’)G(V,E)foreveryedge(a,b)E ifw(a,b)=w thenE’?E’è{(a,b)withweightw} //權(quán)為w的邊不動(dòng) else V’?Vè{vab} //加一個(gè)新的點(diǎn)vab E’?E’è{(a,vab)withweightw}è{(vab,b)withweightw} endifendforBFS(G’(V’,E’),u)S //清空堆棧zvwhileznil then Push(S,z) z(z) ifznilandzV thenz(z) //刪去不在原圖中的頂點(diǎn) endifendwhile //堆棧中從頂?shù)降椎捻旤c(diǎn)序列就是頂點(diǎn)u到頂點(diǎn)v的最短路徑。End堆棧中從頂?shù)降椎捻旤c(diǎn)序列就是頂點(diǎn)u到頂點(diǎn)v的最短路徑。這是因?yàn)樵贕中任何一條從u到v的路徑對(duì)應(yīng)了一條G’中的一條從u到v的路徑。這里，對(duì)應(yīng)指的是，只要把G中這條從u到v的路徑中，每條權(quán)值為2w的邊(a,b)上加上一個(gè)點(diǎn)vab后分為兩條權(quán)值都為w的邊，那么這條路徑就成了G’中的一條從u到v的路徑。并且，這兩條路徑有相同的權(quán)值。反之，G’中任何一條從u到v的路徑也對(duì)應(yīng)了G中的一條從u到v的路徑，只要把新加的點(diǎn)去掉即可。所以，G’中的一條從u到v的最短路徑也對(duì)應(yīng)了G中的一條從u到v的最短路徑，算法正確性得證。因?yàn)樗惴?部分都只需要O(m+n)時(shí)間，其復(fù)雜度滿足要求。假設(shè)我們用一個(gè)有向圖G(V,E)表示主要城市間的鐵路網(wǎng)。有向邊(u,v)表示從城市u到城市v之間有火車直達(dá)。又假設(shè)，不論從城市u到城市v距離多遠(yuǎn)，從u到v，火車只有兩種票價(jià)，一種是慢車票，價(jià)格為c1；另一種是快車票，價(jià)格為c2(>c1)。再假設(shè)，不論從城市u到城市v距離多遠(yuǎn)，坐慢車者需要d1旅行時(shí)間而坐快車者則需d2(<d1)旅行時(shí)間。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(m+n)算法找出一條從起點(diǎn)s到終點(diǎn)t的最佳路徑使得在總的票價(jià)不超過(guò)M的條件下總的旅行時(shí)間最少。你的算法在給出路徑時(shí)需要同時(shí)標(biāo)明路徑上那一條邊坐慢車，那一條邊坐快車。解： 我們注意到，一條最佳路徑一定是一條邊數(shù)最少的路徑。假定p(s,t)是這樣一條路徑。那么，如何決定那一條邊坐慢車，那一條邊坐快車呢？因?yàn)槊織l邊都只有相同的兩種選擇，我們只需決定有幾條邊坐快車即可。下面是偽碼，正確性顯然。Best-Route(G(V,E),c1,c2,d1,d2,M)callBFS(G(V,E),s)togetBFStreeTrootedatsLetp(s,t)bethepathinTfromstotk?|p(s,t)| //邊的個(gè)數(shù)h?0 //坐快車次數(shù)whilec1′(k–h)+c2′h￡M h?h+1endwhileifh=0 thenreturn(Misnotenoughtotravel) //錢不夠旅行 else hh-1 t?d1′(k-h)+d2′h c?c1′(k-h)+c2′hendifreturn{p(s,t),t,c,h} //沿路徑p坐h次快車，其余為慢車。總價(jià)是c，總時(shí)間是tEnd(a)對(duì)下面的有向圖從頂點(diǎn)a開始作DFS搜索并標(biāo)出每個(gè)頂點(diǎn)u的發(fā)現(xiàn)時(shí)刻和完成時(shí)刻d(u)/f(u)。如遇有多種選擇，用字母順序決定。分別列出反向邊集合、前向邊集合、和交叉邊集合中所有邊。列出圖中每個(gè)強(qiáng)連通分支中的頂點(diǎn)并畫出分支圖。解：(a)(b) 反向邊集合={(c,j),(b,a),(h,s),(f,p)}。前向邊集合=空集交叉邊集合={(e,d),(s,g),(g,p),(h,f),(h,m),(h,g)}。各強(qiáng)連通分支及分支圖如下：.假設(shè)我們有n個(gè)盒子，B1，B2，，Bn。盒子Bi(1in)的長(zhǎng)、寬、高分別是Li、Wi、和Di。盒子Bi和盒子Bj如果有Li<Lj、Wi<Wj、和Di<Dj，那么稱盒子Bi兼容于盒子Bj。我們希望從這n個(gè)盒子里選出一組兩兩兼容的盒子使得他們總的容積最大。這也就是說(shuō)，使得Bi∈SLi×Wi×Di最大，這里解：我們構(gòu)造一個(gè)有向圖G(V,E)，其中V={B1，B2，，Bn}{s，t}。這里，頂點(diǎn)Bi代表盒子Bi(1￡i￡n)。如果Li<Lj、Wi<Wj、和Di<Dj，那么就建一條從Bi到Bj的邊(Bi，Bj)并賦以權(quán)值LiWiDi。此外，從s到每個(gè)Bi加一條邊(s,Bi)并賦以權(quán)值0，而從每個(gè)Bi到t加一條邊(Bi,t)并賦以權(quán)值LiWiDi。顯然，構(gòu)造這個(gè)圖的時(shí)間是O(n2)。這個(gè)圖顯然不含回路。圖構(gòu)造好之后，任何一條從s到t的路徑上的頂點(diǎn)，除s和t外，對(duì)應(yīng)了一組兩兩兼容的盒子。而這些盒子的總?cè)莘e恰恰等于路徑上所有邊的權(quán)值總和。因此，找出最長(zhǎng)的一條從s到t的路徑就找到了答案。下面是偽碼。Maximum-Volume(L,W,D,n,S)ConstructG(V,E)asdescribedabove //按上面所述構(gòu)造一圖，顯然無(wú)回路Longest-Path-for-DAG(G(V,E),s) S{v|vpath(s,t),v≠sort}End因?yàn)閳D中最多有n(n-1)/2+2n條邊，而找最長(zhǎng)路徑只需O(n+|E|)時(shí)間，算法復(fù)雜度為O(n2)。重新考慮貪心法一章中的活動(dòng)選擇問(wèn)題。假設(shè)我們有n個(gè)活動(dòng)，a1，a2，，an，申請(qǐng)使用大禮堂。每個(gè)活動(dòng)ai(1￡i￡n)有一個(gè)固定的開始時(shí)間si和一個(gè)完成時(shí)間fi(0si<fi<)。我們假定任何時(shí)候大禮堂只能允許一個(gè)活動(dòng)在進(jìn)行。兩個(gè)活動(dòng)ai和aj稱為兼容，如果它們對(duì)應(yīng)的時(shí)間區(qū)間，[si,fi)和[sj,fj)不相交?，F(xiàn)在我們希望從這n個(gè)活動(dòng)中選出一個(gè)兩兩兼容的子集A使得大禮堂被使用的時(shí)間最長(zhǎng)。注意，與貪心法一章中的活動(dòng)選擇問(wèn)題不同的是，我們不追求集合中活動(dòng)的個(gè)數(shù)最多，而是總時(shí)間最長(zhǎng)，也就是使ai∈A(fi-si)解：Max-Utilization-Activity-Selection(S)構(gòu)造一個(gè)加權(quán)的有向圖G(V,E)，其中V={a1，a2，，an}{s，t}。頂點(diǎn)ai代表活動(dòng)ai(1￡i￡n)。如果fi<sj，那么就建一條從ai到aj的邊(ai，aj)并賦以權(quán)值fi-si。此外，從s到每個(gè)ai加一條邊(s，ai)并賦以權(quán)值0，而從每個(gè)ai到t加一條邊(ai，t)并賦以權(quán)值fi-si。這個(gè)圖顯然無(wú)回路。找出圖中從s到t的最長(zhǎng)路徑P。輸出路徑P上除s和t以外的各頂點(diǎn)所對(duì)應(yīng)的活動(dòng)。End顯然，任何一條從s到t的路徑上的頂點(diǎn)對(duì)應(yīng)一組兩兩兼容的活動(dòng)子集，而任何一組兩兩兼容的活動(dòng)子集也對(duì)應(yīng)了一條從s到t的路徑。而且，一條從s到t的路徑上邊的權(quán)值總和就是路徑上的頂點(diǎn)對(duì)應(yīng)的所有活動(dòng)的時(shí)間總和。所以圖中從s到t的最長(zhǎng)路徑對(duì)應(yīng)的兩兩兼容的活動(dòng)使用大禮堂的總時(shí)間最長(zhǎng)。因此，算法正確。算法用在構(gòu)造圖上的時(shí)間和計(jì)算最長(zhǎng)路徑的時(shí)間都是O(n2)，所以算法復(fù)雜度是O(n2)。(可達(dá)性問(wèn)題)假設(shè)一個(gè)有向圖G=(V，E)的每個(gè)頂點(diǎn)uV都賦與了一個(gè)取自集合{1,2,…,|V|}的整數(shù)標(biāo)號(hào)L(u)。各頂點(diǎn)的標(biāo)號(hào)都不同。對(duì)每個(gè)頂點(diǎn)u，我們定義R(u)={vV|從u到v有路徑}，也就是u可以到達(dá)的所有點(diǎn)的集合。我們?cè)俣xmin(u)為R(u)中標(biāo)號(hào)最小的頂點(diǎn)。即min(u)=v使得L(v)=min{L(w)|wR(u)}。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n+m)算法為每一個(gè)uV算出min(u)。這里，|V|=n，|E|=m。解：讓我們定義有標(biāo)號(hào)L(u)=k的頂點(diǎn)u為vk，k=1，2，…，n。也就是，L(v1)=1，L(v2)=2，…，L(vn)=n，算法如下，證明隨后。Reachability((G(V,E))ConstructtransposegraphGT(V,ET) //構(gòu)造圖G的反置圖foreachvV color(v)Whiteendforfork1ton ifcolor(vk)=White then DFS-visit(GT(V,ET),vk) DFS的附加操作是，為每個(gè)被首次訪問(wèn)的頂點(diǎn)u，做以下操作 min(u)vk //DFS中訪問(wèn)到的點(diǎn)u都有min(u)=vk endifendforEnd正確性證明

: 我們的思路是，第1步找出所有能夠到達(dá)v1的頂點(diǎn)。如果點(diǎn)u可以到達(dá)v1，那么顯然有min(u)=v1，1是最小的標(biāo)號(hào)，因而min(u)就解決了。而且，從點(diǎn)u到v1的路徑上任何一點(diǎn)w也必有min(w)=v1。把所有可到達(dá)v1的路徑合在一起實(shí)際上是一棵以v1為根的樹，樹上每一點(diǎn)w都有min(w)=v1。不過(guò)，這棵樹上的邊的方向都是指向根的方向。那么，在GT中，從點(diǎn)v1為起始點(diǎn)的DFS就正好可以找到這棵樹，也就是DFS樹。第1步之后，如果圖中還有未被DFS訪問(wèn)到的點(diǎn)，那么這些點(diǎn)在原圖G中不可能有路徑到第1步的DFS樹中任何一個(gè)點(diǎn)。所以，我們可以在余下的頂點(diǎn)中重復(fù)第1步的做法。也就是在余下的頂點(diǎn)(白色的點(diǎn))中找一個(gè)標(biāo)號(hào)最小的點(diǎn)vk，從點(diǎn)vk為起始點(diǎn)在轉(zhuǎn)置圖GT中做一輪DFS就正好可以找到所有min(w)=vk的點(diǎn)w。顯然，點(diǎn)vk是這些點(diǎn)能到達(dá)的有最小標(biāo)號(hào)的點(diǎn)。第2步之后，如果圖中還有未被DFS訪問(wèn)到的點(diǎn)，那么這些點(diǎn)在原圖G中不可能有路徑到前2步的DFS所訪問(wèn)過(guò)的點(diǎn)。我們可以在余下的頂點(diǎn)中重復(fù)第1步的做法，直到所有的頂點(diǎn)都被訪問(wèn)到。因?yàn)槊恳惠咲FS都正確地為所訪問(wèn)的點(diǎn)找到可到達(dá)的最小標(biāo)號(hào)，算法正確性得證。重新考慮第6章習(xí)題10。一塊長(zhǎng)方形電路板的上下兩邊各有n個(gè)端口并用數(shù)字從左到右順序標(biāo)為1，2，3，…，n。根據(jù)電路設(shè)計(jì)的要求，我們需要把上邊的n個(gè)端口和下邊的n個(gè)端口配對(duì)用導(dǎo)線連接。假設(shè)與上邊第i個(gè)端口號(hào)連接的下邊的端口號(hào)是π(i)，那么要連接的n個(gè)對(duì)子為(i,π(i))(1≤i≤n)。下面的圖給出了一個(gè)n=8的例子?，F(xiàn)在的問(wèn)題是，找一組導(dǎo)線不相交的對(duì)子，使它含有的對(duì)子最多。比如在下圖中，{(2，1)，(5，2)，(6，5)，(8，7)}就是最大的一組，它含有4個(gè)不相交的對(duì)子。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n2)算法把這個(gè)問(wèn)題轉(zhuǎn)化為一個(gè)圖的問(wèn)題后解出。解：我們構(gòu)造一個(gè)有向圖G(V,E)如下：V={s}{v1，v2，，vn}，其中vi代表線段(i,π(i))(1≤i≤n)。如果(i,π(i))和(j,π(j))(i<j)不相交，畫一條從vi到vj的邊。加一條從源點(diǎn)s到每個(gè)vi(1≤i≤n)的邊。顯然，這個(gè)圖沒(méi)有回路。容易看出，任一條從s出發(fā)的路徑上的點(diǎn)所對(duì)應(yīng)的線段都不會(huì)相交，反之，任何一組不相交的線段，按其上邊端口號(hào)從小到大排序后，加上起始點(diǎn)s，就是一條從s開始的圖G的路徑。所以上面問(wèn)題轉(zhuǎn)化為找一條圖G的最長(zhǎng)路徑問(wèn)題。第8章中有現(xiàn)成的O(n+m)箅法。加上構(gòu)圖時(shí)間，算法復(fù)雜度為O(n2)。(a)有向圖G=(V，E)有n個(gè)頂點(diǎn)，V={v1，v2，，vn}。經(jīng)過(guò)DFS搜索后，每個(gè)頂點(diǎn)vi的發(fā)現(xiàn)時(shí)刻和完成時(shí)刻d(vi)/f(vi)都已標(biāo)出(1￡i￡n)，并分別存在數(shù)組D[1..n]和F[1..n])中?，F(xiàn)在，請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n)時(shí)間的算法，它根據(jù)這n個(gè)區(qū)間把相應(yīng)的DFS樹或森林構(gòu)造出來(lái)。(b) 假設(shè)某有向圖有8個(gè)頂點(diǎn),a，b，c，d，e，f，g，h。經(jīng)過(guò)DFS搜索后，它們的發(fā)現(xiàn)時(shí)刻和完成時(shí)刻如下。請(qǐng)用問(wèn)題(a)中的算法把DFS樹(或森林)畫出來(lái)。a(8/9)，b(13/16)，c(2/3)，d(1/12)，e(4/11)，f(5/6)，g(7/10)，h(14/15)。(c) 假定(e,g)，(b,a)，(h,c)，(a,d)，(f,c)是問(wèn)題(b)中有向圖的邊。請(qǐng)指出它們分別是DFS樹(或森林)里的邊，還是反向邊，還是前向邊，還是交叉邊。解:(a)DFS-Tree(D[1..n],F[1..n],V,T) //D和F分別表示發(fā)現(xiàn)時(shí)刻和完成時(shí)刻CountingsortD[1..n]suchthatD[1]<D[2]<…<D[n]T??StackS??fori?1ton u?Top(S) //指針指向棧頂元素。如果S=?，則u=nil whileu1nilandF[i]>F[u] then Pop(S) u?Top(S) endwhile ifu1nil then T?T{(u,vi)} endif Push(S,vi)endforEnd正確性證明：因?yàn)镈[1..n]和F[1..n])都是正整數(shù)并且不大于2n，所以計(jì)數(shù)排序只需O(n)時(shí)間。排序后，后面的區(qū)間對(duì)應(yīng)的頂點(diǎn)只能是前面某個(gè)點(diǎn)的兒子或者是某一輪DFS樹的根。因?yàn)槊總€(gè)頂點(diǎn)被壓入堆棧只有一次，被彈出最多一次，所以算法有復(fù)雜度O(n)。因?yàn)閰^(qū)間和它對(duì)應(yīng)的頂點(diǎn)是一一對(duì)應(yīng)的，在下面討論中，兩者不作區(qū)分。在for循環(huán)中，我們用堆棧來(lái)鑒別所有的父子關(guān)系，一旦發(fā)現(xiàn)，就有一條樹里的邊。因?yàn)橐婚_始堆棧為空，第一次for循環(huán)后，根(V[1])被壓入堆棧。后面的每次循環(huán)都是在判斷序列中下一個(gè)頂點(diǎn)的父親是誰(shuí)。我們從棧頂開始找。因?yàn)镈[1]<D[2]<…<D[n]，根據(jù)區(qū)間套定理，前面的點(diǎn)不會(huì)是后面的點(diǎn)的兒子。所以如果D[u]<D[i]，但卻有F[u]<F[i]，我們把u從堆棧中彈出，并且再也不需考慮u了。這是因?yàn)楦鶕?jù)區(qū)間套定理，V[i]和V[u]的區(qū)間不相交，必有F[u]<D[i]。V[i]不可能是V[u]的兒子，而后面任一點(diǎn)也不可能。如果F[i]<F[u]，那么V[i]顯然是u的兒子，加上一條樹的邊(u,V[i])。注意，V[i]不可能是更前面的點(diǎn)的兒子，因?yàn)閂[u]的區(qū)間是最小的包含V[i]的區(qū)間。同時(shí)，我們壓入V[i]，因?yàn)樗赡苁呛竺骓旤c(diǎn)的父親。如果堆棧中所有點(diǎn)都被彈出，那么，V[i]自己就是某一輪DFS的根而被壓入堆棧。所以上面算法正確地為每個(gè)兒子找到它的父親，證明畢。(b) (c) 假定(e,g)，(b,a)，(h,c)，(a,d)，(f,c)是上述有向圖的邊。請(qǐng)指出它們分別是DFS樹里的邊，還是反向邊，還是前向邊，還是交叉邊。(e,g)是樹里的邊，(b,a)，(h,c)，(f,c)是交叉邊，(a,d)是反向邊。假設(shè)有一個(gè)nm的棋盤。棋盤中每一格中有一個(gè)數(shù)字并各不相同。我們用數(shù)組A[i，j](1￡i￡n,1￡j￡m)存放這mn個(gè)不同數(shù)字。你可以從某一格運(yùn)動(dòng)到相鄰的一個(gè)格子中去，如果你所在的格子中數(shù)字小于這個(gè)相鄰的格子中數(shù)字。比如，在下面35的棋盤中，你可以從格子(1，1)走到格子(2，1)。連續(xù)的從一個(gè)格子到另一格子的運(yùn)動(dòng)形成一條路徑。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(mn)的算法找出一條最長(zhǎng)的路徑。例如，在下面35的棋盤中，最長(zhǎng)的路徑是(2，2)，(2，3)，(1，3)，(1，4)，(2，4)，(2，5)，(3，5)，(3，4)，(3，3)}。

解：我們定義L[i,j]=以格子(i,j)為終點(diǎn)的最長(zhǎng)的一條路徑的長(zhǎng)度。Longest-Walk(A[1..m,1..n])fori1tom //初始化 forj1ton L[i,j]0 [i,j]nil //父親指針 endforendforConstructadirectedgraphG(V,E),whereV={V[i,j]|1im,1jn},E={(V[i,j],V[i’,j’])|((i=i’and|j–j’|=1)or(|i-i’|=1andj=j’))andA(i,j)<A(i’,j’) //如果格子A[i,j]中的值小于相鄰格子A[i’,j’]中數(shù)字時(shí)，加一條邊。Topological-sort(G(V,E))LetU[1..mn]bethesequence //拓?fù)渑判蚝蟮捻旤c(diǎn)序列fork1tomn (i,j)U[k] //U[k]對(duì)應(yīng)的頂點(diǎn)是V[i,j] dL[i,j]+1 if(V[i,j],V[i,j-1])Eandd>L[i,j-1] then L[i,j-1]d [i,j-1](i,j) endif if(V[i,j],V[i,j+1])Eandd>L[i,j+1] then L[i,j+1]d [i,j+1](i,j) endif if(V[i,j],V[i-1,j])Eandd>L[i-1,j] then L[i-1,j]d [i-1,j](i,j) endif if(V[i,j],V[i+1,j])Eandd>L[i+1,j] then L[i+1,j]d [i+1,j](i,j) endifendforL(u,v)max{L[i,j]|1im,1jn}} //下面是從L(u,v)開始根據(jù)父親指針往回逐步把這條最長(zhǎng)路徑找到。dL(u,v)S //清空堆棧Push(S,(u,v)) while[u,v]nil (u,v)[u,v] Push(S,(u,v))endwhileReturnS,d //堆棧中從頂?shù)降椎脑亟M成這條最長(zhǎng)路徑。因?yàn)閳D中每個(gè)點(diǎn)最多有4條邊，所以構(gòu)造這個(gè)圖和做拓?fù)渑判蚨贾灰狾(mn)時(shí)間。顯然這個(gè)圖是沒(méi)有回路的。所以，只要在這個(gè)圖中找到一條最長(zhǎng)路徑即可。我們按拓?fù)渑判蚝蟮捻樞蛑瘘c(diǎn)訪問(wèn)。每訪問(wèn)一個(gè)點(diǎn)時(shí)，以這點(diǎn)為終點(diǎn)的最長(zhǎng)路徑已知。所以，在訪問(wèn)這點(diǎn)時(shí)，主要工作就是逐一檢查它的鄰居(最多4個(gè))。如果從這點(diǎn)到某個(gè)鄰居可以為這個(gè)鄰居提供更長(zhǎng)路徑的話，則幫這個(gè)鄰居進(jìn)行更新。每個(gè)鄰居都檢查完之后，訪問(wèn)序列中下一個(gè)點(diǎn)。當(dāng)走到下一個(gè)點(diǎn)(i,j)=U[k]時(shí)，所有序列中這點(diǎn)前面的點(diǎn)的最長(zhǎng)路徑都已算出，而且能到達(dá)(i,j)的點(diǎn)也都為(i,j)進(jìn)行了更新的操作。因?yàn)榈竭_(dá)(i,j)的任何路徑必須經(jīng)過(guò)前面的相鄰的某個(gè)點(diǎn)(后向鄰居)，所以當(dāng)訪問(wèn)點(diǎn)(i,j)時(shí)，L[i,j]已經(jīng)算出。因此，算法是正確的。因?yàn)槊總€(gè)點(diǎn)最多需要為4個(gè)鄰居更新，而且更新可以在O(1)時(shí)間內(nèi)完成，算法復(fù)雜度為O(mn)。給定一個(gè)無(wú)回路的有向圖G(V，E)和其中兩個(gè)頂點(diǎn)s和t，我們希望算出一共有多少條不同的從s到t的路徑。我們假定任何兩條路徑，只要有一條邊不同，就是兩條不同路徑。請(qǐng)為此設(shè)計(jì)一個(gè)O(m+n)的算法。算法只要統(tǒng)計(jì)出數(shù)字即可，不需要給出具體路徑。解：下面是算法的偽碼，其正確性顯然。Path-Count(G(V，E),s,t)Topological-Sort(G(V,E),s)LetthesortedsequencebeA[1..h],whereA[1]=s //如果有s不能到達(dá)的點(diǎn)，h<n fori?1toh letu=A[i] count(u)?0 //初始化，count[u]是s到u的路徑數(shù)endforcount(s)?1 //s有一條到自己的路徑fork=1toh-1 letu=A[k] foreachv?Adj(u) count(v)?count(v)+count(u) endforendforreturncount(t)End另一個(gè)對(duì)有向圖G=(V，E)進(jìn)行拓?fù)渑判虻姆椒ㄊ?，先找一個(gè)入度為0的頂點(diǎn)，把它輸出并把這個(gè)頂點(diǎn)連同從它出去的邊全部從圖中刪去。然后，再找一個(gè)入度為0的頂點(diǎn)，把它輸出后，也把它連同從它出去的邊全部從圖中刪去。不斷地這祥做下去直到每個(gè)點(diǎn)都被輸出。請(qǐng)給出一個(gè)O(n+m)的算法來(lái)實(shí)現(xiàn)這個(gè)做法。當(dāng)圖G中有回路時(shí)，會(huì)有什么問(wèn)題

?解: 算法如下：Alternative-Topological-Sort(G(V，E))foreachuV in-degree(u)0 //初始化，然后計(jì)算endforforeach(u,v)E in-degree(v)in-degree(v)+1//計(jì)算in-degree只需O(m)時(shí)間endforQ //清空一個(gè)隊(duì)列foreachuV ifin-degree(u)=0 thenEnqueue(Q,u) //O(n)時(shí)間把所有入度為0的點(diǎn)入隊(duì) endifendforwhileQ uDequeue(Q) outputu //依次輸出隊(duì)列中入度為0的點(diǎn) VV–{u} foreachvAdj(u) in-degree(v)in-degree(v)-1 //邊(u,v)去掉了 ifin-degree(v)=0 thenEnqueue(Q,v) //v是新的入度為0的點(diǎn) endif endfor endwhile //while循環(huán)用時(shí)O(m)ifV //檢查是否有回路 thenreturn(Thereisacycle) //報(bào)告有回路endifEnd顯然算法的復(fù)雜度為O(n+m)。如果有回路，算法仍可進(jìn)行，但那些在回路中的點(diǎn)不可能入度為0。所以算法結(jié)束時(shí)，有些點(diǎn)未被輸出。這些點(diǎn)是強(qiáng)連通分支中的點(diǎn)以及從某個(gè)強(qiáng)連通分支可以到達(dá)的點(diǎn)。如果一個(gè)有向圖G(V，E)中任兩個(gè)頂點(diǎn)，u，v?V，之間有路徑從u到v或從v到u，那么G稱為是半連通的圖(semi-connectedgraph)。請(qǐng)給出一個(gè)O(m+n)的算法來(lái)判斷圖G是否是半連通。你需要證明其正確性并分析時(shí)間復(fù)雜度。解：算法如下：Semi-connected(G(V，E))調(diào)用強(qiáng)連通分支算法算出連通分支C1，C2，…，Ck。構(gòu)造強(qiáng)連通分支圖GC對(duì)強(qiáng)連通分支圖GC中點(diǎn)進(jìn)行拓?fù)渑判颍O(shè)序列為C1，C2，…，Ck。檢查從Ci到Ci+1是否有邊(1￡i￡k-1)。如果都有,則G是半連通的，否則不是。因?yàn)槊恳徊蕉伎梢栽贠(m+n)時(shí)間內(nèi)完成，上面的算法是個(gè)O(m+n)算法。正確性證明如下。正確性證明：我們分兩種情況分析：假設(shè)Ci到Ci+1有邊(1￡i￡k-1)。這種情況下，如果任兩頂點(diǎn)u和v同屬一個(gè)分支，則他們之間無(wú)疑有通路。不然，設(shè)uCi和vCj，i<j，因?yàn)镃i到Ci+1有邊(1￡i￡k-1)，所以從u到v有通路。因此，G是半連通的。假設(shè)對(duì)某個(gè)i，Ci到Ci+1沒(méi)有邊(1￡i￡k-1)。在這種情況下，Ci中的點(diǎn)u與Ci+1中的點(diǎn)v之間沒(méi)有路徑。由以上兩點(diǎn)知，Ci到Ci+1有邊(1￡i￡k-1)是半連通的充要條件，因此算法正確。一個(gè)有向圖G(V，E)的子圖T稱為有向支撐樹，如果它滿足以下條件：它包括所有V中頂點(diǎn)；圖T不含回路；圖T中存在一個(gè)頂點(diǎn)r，稱為T的根，使得從r到任何一個(gè)頂點(diǎn)有唯一的一條簡(jiǎn)單路徑。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n+m)算法來(lái)判斷一個(gè)給定有向圖G(V,E)是否有一個(gè)有向支撐樹。如果有，則找出一個(gè)有向支撐樹。解: 算法如下：Directed-ST(G(V，E))用DFS(G)計(jì)算各頂點(diǎn)uV的發(fā)現(xiàn)和完成時(shí)刻d(u)/f(u);找出最后完成的頂點(diǎn)u，即f(u)=max{f(v)|vV};從頂點(diǎn)u開始再做一遍DFS(G)；如果以u(píng)為根的DFS樹T包含所有V中頂點(diǎn)，那么回答Yes并輸出T，否則回答No；End算法復(fù)雜度顯然是O(n+m)。下面證明其正確性。算法第4步中，如果以u(píng)為根的DFS樹T包含所有V中頂點(diǎn)，顯然這就是一個(gè)以u(píng)為根的有向支撐樹。所以我們只需證明，如果第4步中，以u(píng)為根的DFS樹T不包含所有V中頂點(diǎn)，那么G不存在有向支撐樹。為了用反證法證明，讓我們假設(shè)以u(píng)為根的DFS樹T不包含所有V中頂點(diǎn)，但是有一個(gè)有向支撐樹T*。假設(shè)T*的根是頂點(diǎn)r。因?yàn)橐評(píng)為根的DFS樹T不包含所有頂點(diǎn)，那么集合V’=V–T非空而且沒(méi)有從T中點(diǎn)到V’中點(diǎn)的邊。所以，有向支撐樹T*的根r必定在V’中。因?yàn)闆](méi)有從T中點(diǎn)到V’中點(diǎn)的邊，也就沒(méi)有從點(diǎn)u到點(diǎn)r的路徑，所以點(diǎn)u和點(diǎn)r必屬于不同的強(qiáng)連通分支。因?yàn)轫旤c(diǎn)r是有向支撐樹T*的根，所以，在圖G的分支圖中必有一條從點(diǎn)r所在的分支到其它任何分支的路徑，包括點(diǎn)u所在分支。根據(jù)書中對(duì)強(qiáng)連通分支算法的證明，在所有分支包含的頂點(diǎn)中，也就是集合V的所有頂點(diǎn)中，算法第一步的DFS完成后，有最大完成時(shí)刻的點(diǎn)必定在頂點(diǎn)r所在的分支中。這與f(u)最大矛盾。所以，圖G不存在有向支撐樹。這就證明了算法的正確性。一個(gè)圖G=(V，E)的頂點(diǎn)子集V’íV稱為一個(gè)獨(dú)立集(independentset)，如果E中任何一條邊只與V’中最多一個(gè)點(diǎn)有關(guān)聯(lián)。這也就是說(shuō)，如果V’中任意兩點(diǎn)之間沒(méi)有邊，那么它就是一個(gè)獨(dú)立集。最大獨(dú)立集問(wèn)題就是要找出圖G的一個(gè)含頂點(diǎn)最多的獨(dú)立集。如果G可以是任意一個(gè)圖，那么這是一個(gè)NP-難問(wèn)題。但是，如果G是一棵樹T，那么，這個(gè)問(wèn)題可以在O(n)時(shí)間內(nèi)解決。請(qǐng)?jiān)O(shè)計(jì)一個(gè)這樣的算法。解：我們先介紹一個(gè)貪心法，然后介紹如何用DFS實(shí)現(xiàn)。我們注意到，一個(gè)葉子的頂點(diǎn)一定可以選進(jìn)最大獨(dú)立集，理由見(jiàn)下圖。假設(shè)圖中頂點(diǎn)v是葉子，它聯(lián)到頂點(diǎn)u。如果最佳解中不含v，那么必含u，否則不可能是最大獨(dú)立集。但是，如果它含有u，那么把u換成v后仍然是一個(gè)最大獨(dú)立集。所以，把葉子頂點(diǎn)v選入最大獨(dú)立集不會(huì)錯(cuò)。把葉子v選入最大獨(dú)立集之后，u就不可以選了，所以必須把u及與之相關(guān)聯(lián)的邊全刪除。然后，問(wèn)題變?yōu)樵谑Ｏ聢D中找出最大獨(dú)立集。于是，我們可以重復(fù)以上做法。這個(gè)貪心法可以用以下DFS算法實(shí)現(xiàn)。假定T(V，E)是一棵樹。我們用紅色表示被選入獨(dú)立集中的點(diǎn)，而藍(lán)色表示要?jiǎng)h除的點(diǎn)。規(guī)則如下：如果一個(gè)點(diǎn)沒(méi)有兒子，則給予紅色(選中)。如果一個(gè)點(diǎn)有一個(gè)紅色兒子，則給予藍(lán)色(刪除)。如果一個(gè)點(diǎn)的所有兒子都是藍(lán)色，則給予紅色(選中)。規(guī)則的正確性顯然。在下面的偽碼中，我們給每個(gè)點(diǎn)一個(gè)變量，report，記錄是否有兒子是紅色。一開始，它的值是no。一旦有兒子變紅色，更改為yes。Independent-Set(T(V，E)，s) //s可取任一點(diǎn)foreachu?V //初始化每個(gè)點(diǎn)，不需要白、灰、黑顏色 p(u)?nil report(u)?noendforS? //清空堆棧Push(S,s)whileS1 uTop(S) //不是彈出，而是建立指針 vu’snextneighborinAdj(u) //u的鄰接表中下一個(gè)鄰居v ifv=nil //u的鄰居已全部訪問(wèn)完畢 then Pop(S) ifreport(u)=no then color(u)?Red ifp(u)nil thenreport(p(u))?yes endif else color(u)?Blue endif else (v)u //u是v的父親 Push(S,v) //將v壓棧使得下一步訪問(wèn)v的鄰居 endifendwhilereturn{allRedvertices} //輸出所有紅色的頂點(diǎn)End因?yàn)闃渲羞叺膫€(gè)數(shù)是n-1，所以算法復(fù)雜度是O(n)。一個(gè)圖G=(V，E)的頂點(diǎn)子集V’íV稱為一個(gè)頂點(diǎn)復(fù)蓋(vertexcover)，如果E中任何一條邊都與V’中一個(gè)或兩個(gè)點(diǎn)有關(guān)聯(lián)。最小頂點(diǎn)復(fù)蓋問(wèn)題就是要找出圖G的一個(gè)有最少頂點(diǎn)的頂點(diǎn)復(fù)蓋。如果G可以是任意一個(gè)圖，那么這是一個(gè)NP-難問(wèn)題。但是，如果G是一個(gè)樹T，那么，這個(gè)問(wèn)題可以在O(n)時(shí)間內(nèi)解決。請(qǐng)?jiān)O(shè)計(jì)一個(gè)這樣的算法。解：因?yàn)閳D中一個(gè)獨(dú)立集的補(bǔ)集是一個(gè)頂點(diǎn)復(fù)蓋，反之亦然。所以，找到了圖中的一個(gè)最大獨(dú)立集，取其補(bǔ)集就是本題的解。因此，用與上一題同樣的算法。在算法結(jié)束后，所有藍(lán)色的頂點(diǎn)組成一個(gè)最小頂點(diǎn)復(fù)蓋。下面圖中的樹是對(duì)某個(gè)圖G=(V，E)進(jìn)行雙連通分支算法后得到的DFS樹。每個(gè)頂點(diǎn)u的發(fā)現(xiàn)時(shí)刻d(u)和變量back(u)的值都標(biāo)在圖上。請(qǐng)根據(jù)這個(gè)圖回答下面問(wèn)題。指出所有的斷點(diǎn)。列出所有雙連通分支及各分支中的頂點(diǎn)。 ababcdefghijklmnopq(1/1)(2/1)(3/1)(4/2)(6/6)(7/6)(8/6)(9/6)(11/1)(12/1)(13/12)(14/12)(15/13)(16/13)(17/13)(10/1)(18/1)(19/1)rs(5/5)解：(a)他們是h，i，d，a，f，c。(b) C1={h,n},C2={i,o,q,s},C3={i,d},C4={a,b,d,h,e,j},C5={f,l,p,r},C6={c,f,k},C7={a,c,g,m}。如果刪去連通圖G(V，E)中的一條邊(u，v)后圖不連通，那么這條邊稱為一個(gè)橋(bridge)。例如下面圖中的邊(u，v)就是一個(gè)橋。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n+m)的算法找出圖中所有橋。解：算法如下，正確性顯然。Bridge(G(V,E))BSelectvertexs //任選一點(diǎn)sBi-Component-Component(G(V,E),s) //調(diào)用雙連通分支算法LetthecomponentsbeC1，C2，…，Ck //設(shè)分解為k個(gè)分支fori1tok if|Ci|=1 //只含一條邊的雙連通分支就是一個(gè)橋 thenBBCi endif endfor returnB End假設(shè)S是有向圖G(V,E)中邊的一個(gè)子集，SE，并且S中的邊不形成任何回路。圖G(V,E)稱為是“相對(duì)于集合S的無(wú)回路圖”，如果圖G(V,E)中任何一個(gè)回路都不經(jīng)過(guò)S中的邊。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n+m)的算法以判斷圖G(V,E)是不是相對(duì)集合S的無(wú)回路圖。解：算法如下，證明隨后。 Acyclic-with-Respect-to-S(G(V,E),S)callStrongly-Connected-Component(G(V,E))LetC[1],C[2],…,C[k]bethestrongly-connected-componentsofG(V,E)fori1tok foreachvertexvC[i] component(v)i //賦與每個(gè)頂點(diǎn)它的分支號(hào) endforendforforeachedge(u,v)S ifcomponent(u)=component(v) then returnno endifendforreturnyesEnd上面的算法顯然正確，因?yàn)槿魏我粋€(gè)回路必定存在于某個(gè)強(qiáng)連通分支內(nèi)，而強(qiáng)連通分支內(nèi)的任一條邊必會(huì)被某個(gè)回路通過(guò)。算法的時(shí)間復(fù)雜度可分析如下。第3行的循環(huán)是給每個(gè)頂點(diǎn)打上它所在的分支號(hào)，執(zhí)行n次，總共只需O(n)時(shí)間。第8行的循環(huán)檢查集合S中每條邊是否在某個(gè)強(qiáng)連通分支內(nèi)，總共只需O(|S|)=O(m)時(shí)間。因?yàn)閺?qiáng)連通分支算法需要O(n+m)時(shí)間，所以該算法復(fù)雜度為O(n+m)。在一個(gè)nn的棋盤上，有些方格標(biāo)記為已占用，其余為可用。下面給出了一個(gè)88的棋盤例子。我們用(i,j)表示位于第i行第j列的方格(1≤i,j≤n)。我們用B[i,j]=0表示方格(i,j)已占用，B[i,j]=1表示方格(i,j)可以用。我們還假設(shè)方格(1,1)和(1,n)可以用。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n2)的算法找出從方格(1,1)到(1,n)的一條最短路徑。我們假設(shè)路徑中每一步必須從當(dāng)前的方格進(jìn)入到相鄰的一個(gè)可用的方格，而不可以進(jìn)入到已占用的方格。路徑的長(zhǎng)度是該路徑所經(jīng)過(guò)的方格的個(gè)數(shù)，包括(1,1)和(1,n)。如果不存在從(1,1)到(1,n)的路徑，輸出d=∞。下面圖例顯示了所給88棋盤中從(1,1)到(1,8)的一條最短路徑，其長(zhǎng)度是22。11標(biāo)記為已占用123456782348657解: 我們用廣度優(yōu)先搜索來(lái)解。偽碼如下，正確性顯然。Shortest-Path-in-Chessboard(B[1..n,1..n])fori1ton forj1ton color(i,j)White d(i,j)∞ //從(1,1)到(i,j)的最短路徑，初始長(zhǎng)度為無(wú)窮大 π(i,j)nil endforendforQ //清空隊(duì)列Qcolor(1,1)Greyd(1,1)1Enqueue(Q,(1,1))whileQ≠andcolor(1,n)=White (u,v)Dequeue(Q) //隊(duì)列首項(xiàng)對(duì)應(yīng)的方格 ifu–11andcolor(u-1,v)=WhiteandB[u-1,v]=1 //(u-1,v)在棋盤內(nèi)且可用 then color(u-1,v)=Grey π(u-1,v)(u,v) d(u-1,v)d(u,v)+1 Enqueue(Q,(u-1,v)) endif ifu+1nandcolor(u+1,v)=WhiteandB[u+1,v]=1 then color(u+1,v)=Grey π(u+1,v)(u,v) d(u+1,v)d(u,v)+1 Enqueue(Q,(u+1,v)) endif ifv–11andcolor(u,v-1)=WhiteandB[u,v-1]=1 then color(u,v-1)=Grey π(u,v-1)(u,v) d(u,v-1)d(u,v)+1 Enqueue(Q,(u,v-1)) endif ifv+1nandcolor(u,v+1)=WhiteandB[u,v+1]=1 then color(u,v+1)=Grey π(u,v+1)(u,v) d(u,v+1)d(u,v)+1 Enqueue(Q,(u,v+1) endifendwhileifcolor(1,n)=White thenreturnd=∞ else StackS //準(zhǔn)備輸出路徑 (u,v)(1,n) while (u,v)≠nil Push(S,(u,v)) (u,v)π(u,v) endwhileendifEnd如果d≠∞，那么堆棧S中從頂?shù)降椎脑鼐褪且粭l最短路徑，其長(zhǎng)度是d(1,n)。如下圖所示，在一個(gè)mn的棋盤上，有些方格標(biāo)記為已占用，其余為可用。我們用(i,j)表示位于第i行第j列的方格(1≤i≤m，1≤j≤n)。我們用B[i,j]=0表示方格(i,j)已占用，B[i,j]=1表示方格(i,j)可以用。從一個(gè)可用方格可以走到同一行或同一列的相鄰的可用方格，但任何時(shí)候不可以進(jìn)入到已占用的方格。如果從一個(gè)可用方格可連續(xù)地走到另一個(gè)可用方格，則稱這兩個(gè)可用方格是連通的。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(mn)的算法找出最大的一個(gè)互相連通的可用方格的集合。例如，在下圖中，集合S={(2，4)，(3，3)，(3，4)，(4，2)，(4，3)，(4，4)}就是該圖中最大的一個(gè)互相連通的可用方格的集合。111234823413657可用方格891112567解: 為方便起見(jiàn)，我們先用BFS設(shè)計(jì)一個(gè)子程序Connected-Squares。它為一個(gè)給定的可用方格(i,j)，找出最大的與之連通的可用方格的集合S(i,j)。那么，最大的S(i,j)(1≤i≤m，1≤j≤n)就是本題的解。Connected-Squares(i,j,S(i,j),K(i,j)) //輸入B[i,j]=1，返回S(i,j)，K(i,j)=|S(i,j)|Q //隊(duì)列Q初始化為空Mark(i,j)true //表示(i,j)已被訪問(wèn)過(guò)了S{(i,j)} //方格(i,j)是集合S(i,j)中第一個(gè)可用方格k1 //當(dāng)前集合S(i,j)只有一個(gè)元素Enqueue(Q,(i,j))whileQ≠ (u,v)De-queue(Q) ifu–11andB[u-1,v]=1andMark(u-1,v)=false then Mark(u-1,v)=true SS{(u-1,v)} kk+1 Enqueue(Q,(u-1,v)) endif ifu+1mandB[u+1,v]=1andMark(u+1,v)=false then Mark(u+1,v)=true SS{(u+1,v)} kk+1 Enqueue(Q,(u+1,v)) endif ifv–11andB[u,v-1]=1andMark(u,v-1)=false then Mark(u,v-1)=true SS{(u,v-1)} kk+1 Enqueue(Q,(u,v-1)) endif ifv+1nandB[u,v+1]=1andMark(u,v+1)=false then Mark(u,v+1)=true SS{(u,v+1)} kk+1 Enqueue(Q,(u,v+1)) endifEndwhileS(i,j)SK(i,j)kreturenS(i,j),K(i,j)End下面是主程序。Largest-Set-of-Connected-Squares(B[1..m,1..n],H,h) //輸出最大連通可用方格的集合H,|H|=hfori1tom forj1ton Mark(i,j)false //初始化，標(biāo)記方格還沒(méi)有被訪問(wèn) endforendforHh0fori1tom forj1ton ifB[i,j]=1andMark(i,j)=false Connected-Squares(i,j,S(i,j),K(i,j)) //調(diào)用子程序 ifK(i,j)>h then HS(i,j) hK(i,j) endif endif endforendforReturnH,hEnd算法的正確性顯然。其時(shí)間復(fù)雜度分析如下。因?yàn)槊總€(gè)方格被初始化一次，被檢查一次，從該點(diǎn)去調(diào)用子程序最多一次，其結(jié)果用來(lái)更新H和h一次，所以主程序需要O(mn)時(shí)間。又因?yàn)?，每個(gè)方格被標(biāo)記最多一次，入隊(duì)一次，出隊(duì)一次，和訪問(wèn)4個(gè)鄰居各一次，所以，子程序需要的總時(shí)間是O(mn)時(shí)間。算法符合題目要求。假設(shè)一個(gè)新興城市劃分為nn個(gè)正方形的小區(qū)。下圖是一個(gè)n=8的例子。我們用(i,j)表示位于第i行第j列的小區(qū)(1≤i,j≤n)。用B[i,j]=0表示小區(qū)(i,j)里沒(méi)有學(xué)校，B[i,j]=1表示小區(qū)(i,j)有學(xué)校。從一個(gè)小區(qū)到同一行或同一列的相鄰的小區(qū)有路相連。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(n2)的算法，為每一個(gè)小區(qū)(i,j)(1≤i,j≤n)，計(jì)算出到最近的有學(xué)校的小區(qū)的距離d(i,j)。這里，距離d(i,j)定義為需要經(jīng)過(guò)的小區(qū)個(gè)數(shù)。如果B[i,j]=1，那么小區(qū)(i,j)本身有學(xué)校，所以d(i,j)=0。請(qǐng)參考下圖中更多例子。2213著色的方格表示B[i,j]=1，即小區(qū)(i,j)