計(jì)算機(jī)算法基礎(chǔ) 第2版 課件 第8章 圖的周游算法

1第8

章

圖的周游算法什么是圖的周游

2圖的表示

3廣度優(yōu)先搜索及應(yīng)用

5

無向圖的二著色問題

124. 深度優(yōu)先搜索及應(yīng)用

17拓?fù)渑判?/p>

32無回路有向圖中最長(zhǎng)路徑問題及應(yīng)用

36有向圖的強(qiáng)連通分支的分解

43無向圖的雙連通分支的分解

522許多應(yīng)用問題用圖來描述，因而產(chǎn)生許多與圖有關(guān)的算法問題。例如圖的著色問題，最短路徑問題等。對(duì)一個(gè)圖的每個(gè)點(diǎn)及每條邊按某種順序進(jìn)行逐一訪冋的算法稱為圖的周游算法，是最重要的圖的算法。圖的周游本身不是目的，而是為解決應(yīng)用問題提供快速有效的訪問框架和順序。在解決具體問題時(shí)，往往需要在周游時(shí)加入其他的操作從而得到結(jié)果。介紹兩個(gè)周游算法，它們有線性復(fù)雜度，所以是最優(yōu)的。如能用周游算法直接解決應(yīng)用問題，算法往往是最優(yōu)的。1.什么是圖的周游算法3鄰接表示例153241432565541533212412123544466642212354552.圖的表示

無向圖

有向圖4

鄰接矩陣示例1532414325612354101010101010101110100101112345123540101100000010000110100000001000000006123456

無向圖

有向圖5廣度優(yōu)先搜索(BFS)策略初始，取圖中一點(diǎn)s開始，訪問s。第1步，逐一訪問Adj(s)中所有點(diǎn)，v1，v2，…，vk。第2步，依次訪問Adj(v1)，Adj(v2)，…，Adj(vk)中的點(diǎn)。訪問Adj(u)中頂點(diǎn)v時(shí)，如果v還未被訪問過，稱首次訪問，否則是后續(xù)訪問。首次訪問建立父子關(guān)系，

(v)=u。第3步，逐一訪問前一步被首次訪問的點(diǎn)的前向鄰居。重復(fù)第3步直到某一步?jīng)]有首次被訪問的點(diǎn)為止。顯然，第k步中被首次訪問的點(diǎn)到點(diǎn)s的(最短)距離是k條邊。如果從s開始的一輪BFS不能訪問到圖中所有點(diǎn)，則取一個(gè)未訪問過的點(diǎn)，再做一輪BFS，直到所有點(diǎn)都被訪問到。3.廣度優(yōu)先搜索及應(yīng)用6BFS算法簡(jiǎn)介用白、灰、黑三種顏色表示每個(gè)頂點(diǎn)被訪問的三個(gè)階段：即還未被訪問，剛被訪問，和它的所有前向鄰居都已被訪問。每個(gè)頂點(diǎn)v附兩個(gè)變量，即s到v的(不加權(quán))距離d(v)，和v的父親指針

(v)。初始置d(v)=

，

(v)

=nil，但置d(s)

=0。用隊(duì)列來順序存儲(chǔ)被首次訪問的點(diǎn)。一開始是點(diǎn)s。每次循環(huán)取出隊(duì)首u(yù)，并逐個(gè)訪問Adj(u)中每個(gè)點(diǎn)v。如果v是白色，則是首次訪問，置

(v)

=u，d(v)=d(u)+1，把v變灰色后入隊(duì)。Adj(u)中點(diǎn)全部訪問后，u變黑色。BFS本身在后續(xù)訪問時(shí)不做任何操作，但解具體問題時(shí)，可能需要一些操作。7BFS(G(V,E),s)foreachvertexu

V–{s} //初始化開始

color(u)

White；d(u)

；(u)

nilendforcolor(s)

Gray；d(s)

0；Q

//先把隊(duì)列清空Enqueue(Q,s) //將s進(jìn)隊(duì)，初始化完成while

Q

u

Dequeue(Q) //取出隊(duì)列首項(xiàng) foreachv

Adj(u)

if

color(v)

=White

then

color(v)

Gray

d(v)

d(u)

+1

(v)

u Enqueue(Q,v)

endif

endfor

color(u)

Black

endwhileEnd8

9例：101112無向圖的二著色問題(BSF應(yīng)用舉例)：

把一個(gè)無向圖著色就是給每個(gè)頂點(diǎn)一個(gè)顏色(一個(gè)號(hào)碼)使得每?jī)蓚€(gè)相鄰點(diǎn)的顏色不同。一個(gè)圖如果可以用k個(gè)顏色來著色，則稱它可k-著色。當(dāng)k

3時(shí)，

判斷一個(gè)圖能否k-著色是NP-完全問題。2-著色問題有多項(xiàng)式算法。BFS可解。13圖2-著色的算法簡(jiǎn)介假設(shè)被著色的圖G是個(gè)連通圖。用紅(Red)、藍(lán)(Blue)兩色為圖著色。原BFS中灰色不用，紅、藍(lán)色表示頂點(diǎn)已不是白色了。原BFS中黑色不用，紅點(diǎn)或藍(lán)點(diǎn)出隊(duì)后不可能再入隊(duì)。距離d(u)與本題無關(guān)，省略。起始點(diǎn)s的顏色著為紅色，即color(s)=Red.Adj(u)中點(diǎn)v被首次訪問時(shí)，著色為與父親u相反顏色，用not(color(u))表示。Adj(u)中點(diǎn)v被后續(xù)訪問時(shí)，檢查是否color(u)

=color(v)。如相同，停止著色并報(bào)告不可二著色，否則繼續(xù)。14Two-Color(G(V,E),s)1 foreachu

V2 color(u)

White //每個(gè)頂點(diǎn)初始化為白色3 endfor4 Q

5 color(s)

Red6 Enqueue(Q,s) //初始化完成，s是隊(duì)列中唯一元素，紅色7 whileQ

8

u

Dequeue(Q)9 foreachv

Adj(u)10 ifcolor(v)

=White //v是首次訪問11 then

color(v)

not(color(u))

12

Enqueue(Q,v)13 else if

color(v)

=color(u)//后續(xù)訪問v14

thenreturn(not2-colorable)15 endif

16 endif17 endfor18 endwhile19 return(2-colorable)20 End15二著色算法正確性證明：兩種情形：算法順利完成。

這種請(qǐng)況下，每個(gè)點(diǎn)必定被訪問到并著色。取任一條邊(u,v)?？紤]算法訪問Adj(u)中點(diǎn)v時(shí)情形。如果點(diǎn)v是白色，那么，v是首次訪問。算法第11行保證必有color(u)

color(v)。如果點(diǎn)v不是白色，那么，

這次訪問是后續(xù)訪問。算法必定要檢查color(v)。因?yàn)樗惴ㄎ粗袛?，必有color(u)

color(v)。所以，

如果算法順利完成，圖必定被正確地二著色。(2) 算法中斷運(yùn)行。這種情況下，必有邊(u,v)被檢測(cè)出

color(u)=

color(v)。

(接下頁)16二著色算法正確性證明

(繼續(xù))如果color(u)=

color(v)=Red，那么一條從根s到u的路徑上點(diǎn)的顏色是紅藍(lán)相間，從而有偶數(shù)條邊。同理，也有一條從s到v的有偶數(shù)條邊的路徑。所以，這兩條路徑加上邊(u,v)形成一個(gè)奇回路從而圖不可二著色。如果color(u)=

color(v)=Blue，那么一條從s到u的路徑有奇數(shù)條邊。同理，也有一條從s到v的有奇數(shù)條邊的路徑。所以，這兩條路徑加上邊(u,v)也形成一個(gè)奇回路。所以圖G也不可2-著色。這就證明了，如果算法中斷運(yùn)行，那么圖不可能2-著色。。算法的正確性得證。17深度優(yōu)先搜索(DFS)策略：與BFS同，初始時(shí)，取一個(gè)尚未訪問過的點(diǎn)u

，訪問點(diǎn)u。然后：逐一訪問Adj(u)中點(diǎn)，直到發(fā)現(xiàn)一個(gè)還未訪問過的鄰居v。這是首次訪問，建立父子關(guān)系，置

(v)=u。置

(v)=u后，暫時(shí)不顧u的余下鄰居，而從v出發(fā)去訪問v的鄰居Adj(v)，并遵循一樣的策略：順序訪問Adj(v)中點(diǎn)直到發(fā)現(xiàn)一個(gè)還未訪問過的鄰居。這是一個(gè)遞歸的過程。

如果v沒有鄰居，Adj(v)=

，或者所有鄰居都已在先前被訪問過了，那么DFS又回到u，稱為回溯(backup)。從v回溯到u后，DFS再繼續(xù)訪問Adj(u)中余下鄰居，直到找到下一個(gè)尚未訪問的點(diǎn)，然后重復(fù)第1,2步。當(dāng)Adj(u)中所有點(diǎn)都被訪問完，一輪DFS完成。4.深度優(yōu)先搜索及應(yīng)用18DFS算法簡(jiǎn)介與BFS同，用白、灰、黑三色表示頂點(diǎn)被訪問的三階段。訪問Adj(u)中v時(shí)，如v是白色，為首次訪問，置

(v)=u，v由白變灰。否則為后續(xù)訪問，DFS本身無操作，解應(yīng)用問題時(shí)會(huì)有操作。每個(gè)點(diǎn)u有兩個(gè)事件點(diǎn)，一個(gè)是首次訪問u時(shí)，點(diǎn)u由白變灰，稱為發(fā)現(xiàn)時(shí)刻d(u)。另一個(gè)是Adj(u)中點(diǎn)全部訪問完畢，u由灰變黑，稱為完成時(shí)刻f(u)。

d(u)和f(u)稱為時(shí)間戳。有n個(gè)頂點(diǎn)的圖有2n個(gè)事件點(diǎn)，按發(fā)生順序從1到2n編號(hào)。既使圖需要多輪DFS，這編號(hào)是統(tǒng)一并連續(xù)的。這樣編號(hào)有妙用。分為主程序和子程序。主程序DFS(G)取圖中一個(gè)未訪問過的點(diǎn)u(白色)，并調(diào)用子程序DFS(G,u)進(jìn)行新一輪DFS搜索。當(dāng)圖中所有點(diǎn)都被訪問，算法結(jié)束。19主程序偽碼DFS(G(V,E))for

eachu

V

color(u)

White //初始化每個(gè)點(diǎn)為白色

(u)

nilendfortime

0 //時(shí)間戳初始化為0foreachvertexu

V

if

color(u)

=White //如果白點(diǎn)，則調(diào)用子程序

then

DFS-Visit(u)

endifendforEnd20遞歸形式的DFS子程序DFS-Visit(s)color(s)

Gray //頂點(diǎn)s

由白變灰time

time+1 d(s)

time //頂點(diǎn)s的發(fā)現(xiàn)時(shí)刻foreachv

Adj(s)

ifcolor(v)

=White

then

(v)

s

DFS-Visit(v) //遞歸訪問v

endifendforcolor(s)

Black //對(duì)s的訪問完成

f(s)

time

time+1 //頂點(diǎn)s的完成時(shí)刻

End21定理8.1(區(qū)間套定理)

點(diǎn)u的訪問區(qū)間[d(u),f(u)]包含v的訪問區(qū)間[d(v),f(v)]當(dāng)且僅當(dāng)u是v的祖先。點(diǎn)u和v沒有直系關(guān)系，當(dāng)且僅當(dāng)它們的訪問區(qū)間不相交。證明：由偽碼知，如果v是u的兒子，則有d(u)<d(v)<f(v)<f(u)。

所以有[d(v),f(v)]

[d(u),f(u)]。顯然，如果

u是v的祖先，那么也有[d(v),f(v)]

[d(u),f(u)]。反之，如果[d(v),f(v)]

[d(u),f(u)]，則有

d(u)<d(v)<f(v)<f(u)。說明訪問u的過程中訪問了v，那么v必定是u的后代。如u和v沒有直系關(guān)系，設(shè)d(u)<d(v)，因無直系關(guān)系，u完成前，不會(huì)訪問v。故有

f(u)<d(v)，它們的區(qū)間必不相交。反之，如區(qū)間不相交，設(shè)

f(u)<d(v)，那么點(diǎn)v不可能成為u的后代。

22定理8.2

(白路徑定理)

頂點(diǎn)v成為u的后代，當(dāng)且僅當(dāng)在時(shí)刻d(u)，圖中存在一條從u到v的由白色頂點(diǎn)構(gòu)成的路徑。證明：如果v是u的后代，那么有路徑u，u1，u2，…，,uk，v。其中uk=v。路徑上，u是u1的父親，u1是u2的父親，…，uk-1

是uk的父親。由定理8.1，有d(u)<d(u1)<d(u2)<…<d(uk)<d(v)。這說明在時(shí)刻d(u)時(shí)，路徑上所有點(diǎn)還沒被訪問，因而是白色的。反之，如果在d(u)時(shí)，有一條從u到v的白路徑

u，u1，u2，…，uk，其中uk=v。用歸納法證明，所有點(diǎn)都必然成為u的后代。(接下頁)23定理8.2

(證明繼續(xù))歸納基礎(chǔ)：

因?yàn)樵赿(u)時(shí)，u1是白色的，而當(dāng)u完成時(shí)，u不可以有未訪問的鄰居，所以u(píng)1必然是u的后代。歸納步驟：

假設(shè)u1，u2，…，up(1

p

k-1)都是u的后代，我們證明頂點(diǎn)up+1也必須是u的后代。

為了用反證法，假設(shè)up+1不是u的后代。由定理8.1，頂點(diǎn)up+1的訪問區(qū)間在u的訪問區(qū)間之后。所以，在up完成時(shí)刻，頂點(diǎn)up+1必定仍然是白色的點(diǎn)。這表明，在up完成時(shí)，它還有個(gè)白色的鄰居未訪問，這與算法矛盾。因此，頂點(diǎn)up+1也必須是u的后代，歸納成功。

24非遞歸子程序DFS-Visit(s)簡(jiǎn)介用堆棧保存灰色頂點(diǎn)，s先被訪問、入棧并改灰色。然后每一步都是訪問棧頂S中頂點(diǎn)u的下一個(gè)鄰居直到S=

。設(shè)棧頂是u，DFS訪問Adj(u)中的下一個(gè)頂點(diǎn)。有3種情況：(1) Adj(u)中的所有頂點(diǎn)都己訪問過了。說明DFS-Visit(u)完成，彈出u，u變黑色并賦以f(u)。(2) Adj(u)中的下一個(gè)頂點(diǎn)v是白色的。v被首次訪問，壓入堆棧、變灰色并賦以d(v)，置

(v)=u。可見，堆棧中仼何二個(gè)相鄰元素構(gòu)成父子關(guān)系。所以，堆棧中從底到頂?shù)脑赜趯?duì)應(yīng)的頂點(diǎn)序列是DFS樹中由根開始的一條路徑。(3)

Adj(u)中的下一個(gè)頂點(diǎn)v不是白色的。這是對(duì)v的后續(xù)訪問，DFS本身并不做任何操作，但在解決具體應(yīng)用問題時(shí)，須結(jié)合具體問題而設(shè)計(jì)相應(yīng)的操作。25

26DFS導(dǎo)致的圖中邊的分類在我們完成DFS時(shí)，除了DFS樹或森林，圖中其他的邊往往被忽略。因?yàn)檫@些邊在某些應(yīng)用中有用，我們對(duì)它們進(jìn)行分類。在一個(gè)有向圖中，如果(u,v)不在DFS樹里，v

Adj(u)。它被稱為以下3種邊之一，并且可以在DFS進(jìn)行中被判定：

反向邊(backedge)如果v是u的一個(gè)祖先。判斷條件：v是灰色，或DFS樹中有從v到u的路徑。

前向邊(forwardedge)如果v是u的一個(gè)后代。判斷條件：v是黑色且d(u)<d(v)。

交叉邊(crossedge)如果u和v無直系關(guān)系。判斷條件：v是黑色且d(u)>d(v)。注：無向圖只可能有反向邊。27例8.1

對(duì)下面的有向圖進(jìn)行從頂點(diǎn)a開始的DFS搜索并標(biāo)出各點(diǎn)的發(fā)現(xiàn)時(shí)刻和完成時(shí)刻。當(dāng)搜索中有多個(gè)選擇時(shí)，用字母順序確定。DFS搜索完成后，畫出DFS樹或DFS森林。同時(shí)，對(duì)非樹邊標(biāo)出它的類別。28解：下面圖逐步顯示DFS搜索的過程。當(dāng)DFS發(fā)現(xiàn)頂點(diǎn)u時(shí)，我們?cè)趗的旁邊標(biāo)以d(u)/，而在u的完成時(shí)刻在u的邊上標(biāo)以d(u)/f(u)。2930層3132拓?fù)渑判?Topologicalsort)將一個(gè)無回路的有向圖(DirectedAcyclicgraph,DAG)中的頂點(diǎn)排序，使得該序列的順序和圖中每一條邊都一致：只要(a,b)是圖中一條邊，在序列中，頂點(diǎn)a就一定出現(xiàn)在b的前面。一個(gè)無回路有向圖的例子(圖8-8)離散數(shù)學(xué)計(jì)算機(jī)原理操作系統(tǒng)體系結(jié)構(gòu)計(jì)算機(jī)算法知識(shí)產(chǎn)權(quán)數(shù)據(jù)結(jié)構(gòu)邏輯設(shè)計(jì)C++語言匯編語言33上例描述了計(jì)算機(jī)系研究生應(yīng)修的10門課之間的關(guān)系。邊(a,b)表明，必須先完成課程a才可以選b。假設(shè)某研究生每學(xué)期只能上一門課，他應(yīng)該按照什么順序來選這10門課程使得他能在10個(gè)學(xué)期內(nèi)完成所有課程并且在每學(xué)期上課時(shí)，所有前序課程都已完成？拓?fù)渑判蛩惴═opological-Sort(G(V,E))建一個(gè)空的鏈表L。調(diào)用DFS(G(V,E))對(duì)圖G進(jìn)行深度優(yōu)先搜索。DFS進(jìn)行中的附加操作是，在每個(gè)頂點(diǎn)的完成時(shí)刻，將該頂點(diǎn)插入到鏈表L的頭部。順序輸鏈表L中各頂點(diǎn)。5

End該算法實(shí)際上是把頂點(diǎn)按它們的完成時(shí)刻，從大到小排序。34例:對(duì)上面有向圖作拓?fù)渑判虻慕Y(jié)果如下：離散數(shù)學(xué)計(jì)算機(jī)原理邏輯設(shè)計(jì)計(jì)算機(jī)算法C++語言匯編語言操作系統(tǒng)體系結(jié)構(gòu)知識(shí)產(chǎn)權(quán)數(shù)據(jù)結(jié)構(gòu)12/194/75/61/82/313/1815/169/1011/2014/17數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)原理匯編語言C++語言離散數(shù)學(xué)(1)(2)(3)(4)(5)操作系統(tǒng)計(jì)算機(jī)算法邏輯設(shè)計(jì)體系結(jié)構(gòu)知識(shí)產(chǎn)權(quán)(6)(7)(8)(9)(10)35拓?fù)渑判蛩惴ㄕ_性證明：我們只需證明，一條邊(u,v)中的兩頂點(diǎn)u和v，一定會(huì)先輸出v，后輸出u，即f(v)<f(u)。我們分兩種情況討論：(1) d(u)<d(v)。發(fā)現(xiàn)u時(shí)，v是u的一個(gè)白色的鄰居。由白路徑定理，v將是u的后代，所以有f(v)<f(u)。(2) d(v)<

d(u)。發(fā)現(xiàn)v時(shí)，u是v的一個(gè)白色的鄰居。由于圖G無回路，不存在從v到u的路徑，更沒有白路徑。所以，在DFS完成對(duì)v的訪問之后，即時(shí)刻f(v)之后，才有可能去發(fā)現(xiàn)u。所以有f(v)<f(u)。因此，算法Topological-Sort(G(V,E))是正確的。36無回路有向圖中最長(zhǎng)路徑問題及應(yīng)用許多應(yīng)用問題需要找圖中兩點(diǎn)間的最短或最長(zhǎng)的簡(jiǎn)單路徑。找最短路徑是個(gè)比較容易的問題。不加權(quán)的圖，一次BFS搜索就可以找到。加權(quán)的圖，第10章會(huì)討論兩個(gè)知名算法。找圖中最長(zhǎng)路徑是一個(gè)NP-完全問題，既使圖不加權(quán)。但是，如果圖沒有回路，那么無論是有向圖或無向圖，加權(quán)或不加權(quán)，權(quán)值為正或?yàn)樨?fù)，找最長(zhǎng)或最短路徑的問題都可以在線性時(shí)間O(|V|+|E|)=O(n+m)里解決。因?yàn)闊o回路的無向圖是棵樹或森林，問題顯然可在O(n)時(shí)間里解決，所以我們假定圖G是一個(gè)加權(quán)的有向圖。下面的算法計(jì)算從頂點(diǎn)s到圖G中其他各點(diǎn)的最長(zhǎng)簡(jiǎn)單路徑。37Longest-Path-for-DAG(G(V,E),s) for

eachv

V

d(v)

-

，

(v)

nil

//初始化endforTopological-Sort(G(V,E),s) //從s開始的拓?fù)渑判騆etv1(=s),v2,v3,....,vk,

bethesequencefromtopologicalsortd(s)

0for

i

1tok-1 foreachu

Adj(vi)

if

(d(vi)+w(vi,u))>d(u)

then

d(u)

d(vi)+w(vi,u)

(u)

vi

endif

endforendforEnd

38無回路有向圖中最長(zhǎng)路徑的應(yīng)用例子劇場(chǎng)內(nèi)有兩個(gè)電影院X和Y。在t

=0開始的一周內(nèi)，X會(huì)順序放映長(zhǎng)短不一的電影x1，x2，…，xn，其每場(chǎng)開始和結(jié)束時(shí)間順序?yàn)?a1，b1)，(a2，b2)，…，(an，bn)。同一周內(nèi)，Y會(huì)連續(xù)放映m個(gè)電影，y1，y2，…，ym。其每場(chǎng)開始和結(jié)束時(shí)間順序?yàn)?c1，d1)，(c2，d2)，…，(cm，dm)。每位觀眾必須準(zhǔn)時(shí)入場(chǎng)并不得中途退場(chǎng)。又假定兩電影院之間距離極近，覌眾從一個(gè)影院走到另一個(gè)影院所需時(shí)間為零?，F(xiàn)在，我們要從兩個(gè)影院中選出一組時(shí)間互不沖突的電影使得一個(gè)觀眾可以一個(gè)接一個(gè)地看完這些電影，并且使得這個(gè)觀眾看電影的總時(shí)間最長(zhǎng)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)O(m+n)的算法。39解：

構(gòu)造有向圖G(V,E)如下：V

={x1，x2，…，xn，y1，y2，…，ym，s，t}。xi代表電影xi(1

i

n)，yj

代表電影yj(1

j

m)。頂點(diǎn)s和t代表起點(diǎn)和終點(diǎn)。邊由下面7部分組成：(xi，xi+1)(1

i

n-1)，權(quán)值為w(xi，xi+1)=bi-ai。(yj,yj+1)(1

j

m-1)，權(quán)值為w(yj,yj+1)=dj–cj。(xi,yj)(1

i

n-1)，權(quán)值為w(xi,yj)=bi-ai，如果yj是第一個(gè)滿足bi

cj的電影。(yj，xi)(1

j

m-1)，權(quán)值為w(yj，xi)=dj–cj，如果xi是第一個(gè)滿足dj

ai的電影。從頂點(diǎn)s分別有一條到x1和y1的邊并有權(quán)值0。從頂點(diǎn)xn有一條到t的邊(xn，t)并有權(quán)值w(xn，t)=bn–an。從頂點(diǎn)ym有一條到t的邊(ym，t)并有權(quán)值w(ym，t)=dm–cm。40構(gòu)造有向圖G(V,E)的算法Construction-G(X,Y,A,B,C,D,m,n)V

{x1，x2，…，xn，y1，y2，…，ym，s，t}E

for

i

1to

n-1

E

E

{(xi,xi+1)withw(xi,xi+1)=(bi-ai)}endforfor

j

1to

m-1

E

E

{(yj,yj+1)withw(yj,yj+1)=(dj–cj)}endforE

E

{(s,x1)withw(s,x1)=0,(s,y1)withw(s,y1)=0}E

E

{(xn,t)withw(xn,t)=bn–an,(ym,t)withw(ym,t)=dm–cm}

i

j

1 //開始構(gòu)造從影院X到影院Y的邊

(接下頁)41構(gòu)造有向圖G(V,E)的算法(繼續(xù))while

i

nand

j

m

if

bi

cj

then

E

E

{(xi,yj)withw(xi,yj)=(bi-ai)，i

i+1

else

j

j+1

endifendwhilej

i

1 //開始構(gòu)造從影院Y到影院X的邊while

j

mand

i

n

if

dj

ai

then

E

E

{(yj,xi)withw(yj,xi)=(dj–cj)，j

j+1

else

i

i+1

endifendwhilereturnG(V,E)End42算法Construction-G的復(fù)雜度分析第3行和第6行的兩個(gè)for循環(huán)分別有復(fù)雜度O(n)和O(m)。上頁(書上第12行)的while循環(huán)有復(fù)雜度O(n+m)，這是因?yàn)槊垦h(huán)一次，指針i或j就要加1，因此總共最多有m+n次循環(huán)。同理，另一個(gè)(書上第20行)的while循環(huán)有復(fù)雜度O(n+m)。

所以，算法Construction-G的復(fù)雜度是O(n+m)?？措娪皢栴}的解：圖G(V,E)構(gòu)造好之后，任何一個(gè)合理的解對(duì)應(yīng)著一條從起點(diǎn)s到終點(diǎn)t的一條路徑，反之亦然。這里，“合理”意味著不故意跳過一個(gè)可看電影，因?yàn)檫@樣做顯然不會(huì)最優(yōu)。所以，圖中一條最長(zhǎng)路徑對(duì)應(yīng)最佳解。因?yàn)闊o回路并且頂點(diǎn)和邊的個(gè)數(shù)分別都是O(n+m)，我們可用Longest-Path-for-DAG(G(V,E),s)算法在O(n+m)時(shí)間內(nèi)找到最佳解。43有向圖的強(qiáng)連通分支分解如果任一頂點(diǎn)都有一條通向其他任一頂點(diǎn)的路徑，那么這個(gè)有向圖稱為一個(gè)強(qiáng)連通圖(StronglyConnectedGraph)。如果一個(gè)有向圖的子圖是個(gè)強(qiáng)連通圖，則稱為強(qiáng)連通子圖(StronglyConnectedSubgraph)。如果一個(gè)強(qiáng)連通子圖已最大化，即不能再加入其他任何一個(gè)頂點(diǎn)而仍然強(qiáng)連通，那么這個(gè)子圖稱為強(qiáng)連通分支(StronglyConnectedComponent)。有向圖的強(qiáng)連通分支問題就是把一個(gè)有向圖的頂點(diǎn)劃分為不相交的若干個(gè)強(qiáng)連通分支。44例bcefgda(a)一個(gè)有向圖bcefgda(b)分解為兩個(gè)強(qiáng)連通分支強(qiáng)連通分支分解算法見下頁45Strongly-Connected-Component(G(V,E))對(duì)G進(jìn)行DFS搜索并按完成時(shí)刻，從大到小，排序?yàn)?/p>

f(v1)

>f(v2)

>…>f(vn)。2 構(gòu)造G的轉(zhuǎn)置圖GT(V,E’)，其中，V不變，邊的集合E’是把E中每條邊反向后得到，即E’={(u,v)|(v,u)

E}。把所有GT中頂點(diǎn)著以白色。順序檢查序列v1，v2，…，vn。如果vk

(1

k

n)仍是白色，則從vk開始，對(duì)圖GT進(jìn)行一輪DFS搜索。所有在這一輪首次訪問到的頂點(diǎn)，也就是在這一輪變黑色的頂點(diǎn)，形成一個(gè)強(qiáng)連通分支，將其輸出。繼續(xù)第4步直到所有點(diǎn)都被輸出。End //算法的復(fù)雜度顯然是O(m+n)46例8.4

對(duì)例8.1中有向圖頂點(diǎn)進(jìn)行強(qiáng)連通分支分解。頂點(diǎn)序列： a，g，h，s，k，e，d，b，p，m，f，c，j。474849強(qiáng)連通分支算法證明：先介紹強(qiáng)連通分支圖，簡(jiǎn)稱分支圖。分支圖GC(VC,EC)中每個(gè)頂點(diǎn)u

VC

代表一個(gè)強(qiáng)連通分支。邊(u,v)

EC

當(dāng)且僅當(dāng)在原圖G(V,E)中有一條從分支u中頂點(diǎn)到分支v中頂點(diǎn)的邊。分支圖無回路，否則回路上的所有分支都應(yīng)屬于同一連通分支。例前面例子的分支圖（不是GT的分支圖）：a,d,

ep,f,

mg,s,

h,kb,j,

c(接下頁)50強(qiáng)連通分支算法證明

(繼續(xù)1)現(xiàn)在證明，如果圖G的分支圖中有邊(u,v)，那么，分支u和分支v的所有頂點(diǎn)中，有最大完成時(shí)刻的點(diǎn)必定落在分支u中。分兩種情況討論：這些頂點(diǎn)中，最先發(fā)現(xiàn)的頂點(diǎn)x在分支u中。因u和v強(qiáng)連通，又有邊(u,v)，x有路徑到達(dá)u

和v中任何一個(gè)點(diǎn)。所以，在時(shí)刻d(x)，x有白路徑到達(dá)u

和v中任何一點(diǎn)。因此，這些點(diǎn)都是x的后代，因而對(duì)x的訪問最后完成。這些頂點(diǎn)中，最先被發(fā)現(xiàn)的頂點(diǎn)x在分支v中。因?yàn)榉种D無回路，所以x沒有到分支u中點(diǎn)的路徑。當(dāng)分支v中點(diǎn)都完成時(shí)，u中的點(diǎn)仍然都是白色的。所以，最后完成的點(diǎn)也必定落在分支u中。證畢。(接下頁)51強(qiáng)連通分支算法證明(繼續(xù)2)設(shè)算法對(duì)圖G的DFS最后完成的頂點(diǎn)x在分支u，那么在圖G中只有從分支u出去的邊而沒有進(jìn)來的邊。由于強(qiáng)連通分支的劃分在轉(zhuǎn)置圖GT中不變，所以分支u在GT中只有進(jìn)來的邊而沒有出去的邊。所以，從x開始對(duì)GT作DFS搜索時(shí)，分支u中所有點(diǎn)會(huì)被訪問到，但跑不出分支u。所以，第一輪DFS正好把分支u分離出來。第二輪DFS從分支u以外的點(diǎn)中最后完成的頂點(diǎn)y開始。也就是算法第一步產(chǎn)生的序列f(v1)>f(v2)>…>f(vn)中，第一個(gè)仍然還是白色的頂點(diǎn)。那么，除分支u以外(u中點(diǎn)已黑色)，點(diǎn)y所在的分支在GT中只有進(jìn)來的邊而沒有出去的邊。這樣，第二輪DFS便正確地分離了這個(gè)分支。依次類推，每一輪DFS正確分離一個(gè)強(qiáng)連通分支，直止所有點(diǎn)被訪問到。

52無向圖的雙連通分支的分解一個(gè)頂點(diǎn)稱為斷點(diǎn)，如果把這個(gè)點(diǎn)及與之相關(guān)聯(lián)的邊從圖中刪去后，這個(gè)圖不連通。沒有斷點(diǎn)的圖稱為雙連通圖。一個(gè)子圖稱為雙連通子圖，如果它是雙連通的。一個(gè)子圖稱為雙連通分支，如果它是雙連通的并且最大化。雙連通分支的分解是對(duì)邊的一種劃分。例53上圖(a)可分解為兩個(gè)雙連通分支。下面的觀察可幫助我們把斷點(diǎn)識(shí)別出來。(1)

DFS樹中任一個(gè)葉子頂點(diǎn)不可能是斷點(diǎn)。(2) DFS樹的根是斷點(diǎn)，當(dāng)且僅當(dāng)它有兩個(gè)或更多的兒子。(3) DFS樹中根以外的內(nèi)結(jié)點(diǎn)u是一個(gè)斷點(diǎn)，當(dāng)且僅當(dāng)它的某個(gè)子樹中的點(diǎn)沒有反向邊指向u的祖先(u本身不算)。54下圖幫助解釋上面第3條55雙連通分支分解算法簡(jiǎn)介用DFS，但不記錄完成時(shí)刻，發(fā)現(xiàn)時(shí)刻d(u)從1到n標(biāo)記。用變量back(u)記錄點(diǎn)u的一個(gè)反向邊，或者u的任一個(gè)后代x的一個(gè)反向邊能達(dá)到的最高祖先的高度。

back(u)=min{d(w)|w=u

或u的后代x有反向邊(x,w)}。u本身也算作它自己的后代，所以有back(u)≤d(u)。計(jì)算和更新back(u)的做法：當(dāng)u被發(fā)現(xiàn)時(shí)，置back(u)

d(u)。當(dāng)發(fā)現(xiàn)一條反向邊(u,a)時(shí)，更新back(u):

back(u)

min{d(a)，back(u)}當(dāng)u的一個(gè)兒子v回溯到u時(shí)，如果back(v)<d(u)，那么back(u)

min{back(v)，back(u)}。56斷點(diǎn)識(shí)別與分支的切割當(dāng)v回溯到u時(shí)，如果back(v)

d(u)，那么，u是斷點(diǎn)。把以v為根的子樹T(v)以及邊(u,v)從當(dāng)前的DFS樹中割開(一裂為二)。由于DFS的遞歸性，從u裂開時(shí)，子樹T(v)中其他斷點(diǎn)都已在早先被識(shí)別，而相應(yīng)的雙連通分支也已被切割。當(dāng)前切下的分支所包含的邊是，從訪問邊(u,v)開始，到v回溯到u為止，除去已切割的分支，DFS訪問過的所有邊。我們專門用一個(gè)堆棧S’來保留訪問過的邊。當(dāng)一個(gè)分支被切割時(shí)，它的邊被彈出。當(dāng)v回溯到u時(shí)，如果發(fā)現(xiàn)back(v)

d(u)，彈出堆棧S’中邊直到邊(u,v)被彈出。當(dāng)u是DFS樹根時(shí)以上做法也正確，它會(huì)把DFS樹根的每一個(gè)子樹從根裂開并形成一個(gè)雙連通分支。(算法見下頁)57Bi-Connected-Component(G(V,E),s) //G為連通圖，s可任取for

eachu

V

//DFS初始化開始

color[u]

White；

[u]

nilendforcolor(s)

Gray；

time

1 //時(shí)間戳從1開始back(s)

d(s)

timek

0 //雙連通分支編號(hào)，將從1開始

S

S’

；

//DFS所用堆棧和邊的堆棧清空Push(S,s) //初始化完成，點(diǎn)s入棧while

S≠

u

Top(S) //不是彈出，而是建立指針 v

u’snextneighborinAdj(u) //u的下一個(gè)鄰居v

if

v≠nil

//u還有鄰居未被訪問

thenifcolor(v)

=White //

首次訪問v，v是白色的

(接下頁)58Bi-Connected-Component

(繼續(xù))

then

time

time+1;

d(v)

time

back(v)

d(v)

//初始化back(v)

(v)

u,

color(v)

=Gray

Push(S,v)，Push(S’,(u,v))

else back(u)

min{back(u),d(v)}//反向邊

Push(S’,(u,v))

endif

else

color(u)

Black,

Pop(S)

ifS≠ //u有父親

then

w

Top(S) //父親是w

if

back(u)<d(w)