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

1第8

章

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

2圖的表示

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

5

無向圖的二著色問題

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

17拓撲排序

32無回路有向圖中最長路徑問題及應用

36有向圖的強連通分支的分解

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

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

無向圖

有向圖4

鄰接矩陣示例1532414325612354101010101010101110100101112345123540101100000010000110100000001000000006123456

無向圖

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

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

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

，

(v)

=nil，但置d(s)

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

(v)

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

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

color(u)

White；d(u)

；(u)

nilendforcolor(s)

Gray；d(s)

0；Q

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

Q

u

Dequeue(Q) //取出隊列首項 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應用舉例)：

把一個無向圖著色就是給每個頂點一個顏色(一個號碼)使得每兩個相鄰點的顏色不同。一個圖如果可以用k個顏色來著色，則稱它可k-著色。當k

3時，

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

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

V2 color(u)

White //每個頂點初始化為白色3 endfor4 Q

5 color(s)

Red6 Enqueue(Q,s) //初始化完成，s是隊列中唯一元素，紅色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二著色算法正確性證明：兩種情形：算法順利完成。

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

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

這次訪問是后續(xù)訪問。算法必定要檢查color(v)。因為算法未中斷，必有color(u)

color(v)。所以，

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

color(u)=

color(v)。

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

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

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

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

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

(v)=u。置

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

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

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

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

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

eachu

V

color(u)

White //初始化每個點為白色

(u)

nilendfortime

0 //時間戳初始化為0foreachvertexu

V

if

color(u)

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

then

DFS-Visit(u)

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

Gray //頂點s

由白變灰time

time+1 d(s)

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

Adj(s)

ifcolor(v)

=White

then

(v)

s

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

endifendforcolor(s)

Black //對s的訪問完成

f(s)

time

time+1 //頂點s的完成時刻

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

點u的訪問區(qū)間[d(u),f(u)]包含v的訪問區(qū)間[d(v),f(v)]當且僅當u是v的祖先。點u和v沒有直系關(guān)系，當且僅當它們的訪問區(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完成前，不會訪問v。故有

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

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

22定理8.2

(白路徑定理)

頂點v成為u的后代，當且僅當在時刻d(u)，圖中存在一條從u到v的由白色頂點構(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)。這說明在時刻d(u)時，路徑上所有點還沒被訪問，因而是白色的。反之，如果在d(u)時，有一條從u到v的白路徑

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

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

因為在d(u)時，u1是白色的，而當u完成時，u不可以有未訪問的鄰居，所以u1必然是u的后代。歸納步驟：

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

p

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

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

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

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

(v)=u?？梢?，堆棧中仼何二個相鄰元素構(gòu)成父子關(guān)系。所以，堆棧中從底到頂?shù)脑赜趯捻旤c序列是DFS樹中由根開始的一條路徑。(3)

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

26DFS導致的圖中邊的分類在我們完成DFS時，除了DFS樹或森林，圖中其他的邊往往被忽略。因為這些邊在某些應用中有用，我們對它們進行分類。在一個有向圖中，如果(u,v)不在DFS樹里，v

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

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

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

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

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

End該算法實際上是把頂點按它們的完成時刻，從大到小排序。34例:對上面有向圖作拓撲排序的結(jié)果如下：離散數(shù)學計算機原理邏輯設(shè)計計算機算法C++語言匯編語言操作系統(tǒng)體系結(jié)構(gòu)知識產(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)計算機原理匯編語言C++語言離散數(shù)學(1)(2)(3)(4)(5)操作系統(tǒng)計算機算法邏輯設(shè)計體系結(jié)構(gòu)知識產(chǎn)權(quán)(6)(7)(8)(9)(10)35拓撲排序算法正確性證明：我們只需證明，一條邊(u,v)中的兩頂點u和v，一定會先輸出v，后輸出u，即f(v)<f(u)。我們分兩種情況討論：(1) d(u)<d(v)。發(fā)現(xiàn)u時，v是u的一個白色的鄰居。由白路徑定理，v將是u的后代，所以有f(v)<f(u)。(2) d(v)<

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

eachv

V

d(v)

-

，

(v)

nil

//初始化endforTopological-Sort(G(V,E),s) //從s開始的拓撲排序Letv1(=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無回路有向圖中最長路徑的應用例子劇場內(nèi)有兩個電影院X和Y。在t

=0開始的一周內(nèi)，X會順序放映長短不一的電影x1，x2，…，xn，其每場開始和結(jié)束時間順序為(a1，b1)，(a2，b2)，…，(an，bn)。同一周內(nèi)，Y會連續(xù)放映m個電影，y1，y2，…，ym。其每場開始和結(jié)束時間順序為(c1，d1)，(c2，d2)，…，(cm，dm)。每位觀眾必須準時入場并不得中途退場。又假定兩電影院之間距離極近，覌眾從一個影院走到另一個影院所需時間為零?，F(xiàn)在，我們要從兩個影院中選出一組時間互不沖突的電影使得一個觀眾可以一個接一個地看完這些電影，并且使得這個觀眾看電影的總時間最長。請設(shè)計一個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)。頂點s和t代表起點和終點。邊由下面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是第一個滿足bi

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

j

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

ai的電影。從頂點s分別有一條到x1和y1的邊并有權(quán)值0。從頂點xn有一條到t的邊(xn，t)并有權(quán)值w(xn，t)=bn–an。從頂點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的復雜度分析第3行和第6行的兩個for循環(huán)分別有復雜度O(n)和O(m)。上頁(書上第12行)的while循環(huán)有復雜度O(n+m)，這是因為每循環(huán)一次，指針i或j就要加1，因此總共最多有m+n次循環(huán)。同理，另一個(書上第20行)的while循環(huán)有復雜度O(n+m)。

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

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中頂點著以白色。順序檢查序列v1，v2，…，vn。如果vk

(1

k

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

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

VC

代表一個強連通分支。邊(u,v)

EC

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

ep,f,

mg,s,

h,kb,j,

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

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

和v中任何一個點。所以，在時刻d(x)，x有白路徑到達u

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

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

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

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

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

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

back(u)

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

min{back(v)，back(u)}。56斷點識別與分支的切割當v回溯到u時，如果back(v)

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

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

eachu

V

//DFS初始化開始

color[u]

White；

[u]

nilendforcolor(s)

Gray；

time

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

d(s)

timek

0 //雙連通分支編號，將從1開始

S

S’

；

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

S≠

u

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

u’snextneighborinAdj(u) //u的下一個鄰居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)