6.6-有向圖的DFS與分塊匯總課件

1、6.6有向圖的DFS算法與圖的塊劃分 DFS(depth first search深度優(yōu)先搜索)在2.2中判斷二點(diǎn)之間是否連續(xù)時(shí)使用過: 從某一點(diǎn)出發(fā)v0, 找v0一個(gè)直接下代v1, father(v1)=v0, 找v1未搜索的直接后繼v2, father(v2)=v1, 當(dāng)vj沒有未搜索后代時(shí),回到father(vj),找vj父結(jié)點(diǎn)的另一個(gè)未搜索后代，直到不能搜索后再退回到上一級(jí)。 可用棧記錄搜索過程，現(xiàn)提出更加詳細(xì)的算法，并用來解決有向圖的分塊問題。 當(dāng)從結(jié)點(diǎn)v選擇一條未檢查邊時(shí)可能: (1)w未訪問,則為樹邊; (2)w已訪問,則: (2.1)DFS森林中w是v的子孫,是向前邊; (2.

2、2)DFS森林中w是v的祖先,是回退邊; (2.3)DFS森林中w與v無關(guān),且dfn(w)dfn(v), 則是橫跨邊; 無關(guān)，且w先于v訪問,只能dfn(w)dfn(v)12345678913111012 當(dāng)從結(jié)點(diǎn)v選擇一條未檢查邊時(shí)可能: (1)w未訪問,則為樹邊; (2)w已訪問,則: (2.1)在DFS森林中w是v的子孫,是向前邊; (2.2)在DFS森林中w是v的祖先,是回退邊; (2.3)在DFS森林中w與v無關(guān)且dfn(w)dfn(v), 則是橫跨邊; 只有4種邊。 若dfn(w)dfn(v)即w晚于v訪問,則為樹邊/向前邊 若dfn(w)dfn(v)即w早于v訪問,則為回退邊或橫

3、跨邊12345678913111012編程實(shí)現(xiàn)時(shí)，需要的數(shù)組為：(1)已訪問結(jié)點(diǎn)的數(shù)組MARK(2)已訪問點(diǎn)的父結(jié)點(diǎn)的數(shù)組FATHER(3)深度優(yōu)先指標(biāo)數(shù)組DFN。 僅在結(jié)點(diǎn)x第一次被訪問時(shí)給DFN(x) 賦值。 如果x是第i個(gè)被賦值的結(jié)點(diǎn)，則DFN(x)=I(4)點(diǎn)的邊是否全掃描SCAN,區(qū)分回退邊與橫跨 (5)樹邊(同棵樹中結(jié)點(diǎn)首次訪問所用邊)TREE。(6)向前邊(同樹,指向晚訪問點(diǎn)邊)FORWARD。(7)回退邊(同樹,指向早訪問點(diǎn)的邊) BACK。(8)橫跨邊(指向前棵中早已訪問的邊CROSS(9)邊已訪問EDGE1.Tree=Cross=Back=Forward=,i=1,Fath

4、er(v)=0,Mark(v)=0,Scan(v)=0,dfn(v)=0,edge(e)=02. 任選滿足Mark(r)=0的結(jié)點(diǎn)r(確定新根),置其 DFN(r)=i,Mark(r)=1,v=r(當(dāng)前結(jié)點(diǎn))3.若以v起點(diǎn)的邊都已查,scan(v)=1轉(zhuǎn)5, 否則任選未查邊(v,w)轉(zhuǎn)44.邊(v,w)標(biāo)為已查Edge(v,w)=1,執(zhí)行以下操作后回到3 4.1若Mark(w)=0(未訪),則 i=i+1, DFN(w)=i, Tree=Tree Mark(w)=1, father(w)=v, v=w(修改新當(dāng)前結(jié)點(diǎn)) 4.2 若Mark(w)=1(已訪), 若DFN(w)DFN(v)(w晚)

5、 則Forward=Forward 若DFN(w)DFN(v) (w早)且SCAN(w)=0 則Back=Back 若DFN(w)DFN(v)且SCAN(w)=1 則Cross=Cross5. 若fahter(v)0(不是根)則v=fahter(v)轉(zhuǎn)3，否則轉(zhuǎn)66.若所有結(jié)點(diǎn)Mark(x)=1結(jié)束,否i=i+1轉(zhuǎn)21.Tree=Cross=Back=Forward=,i=1,Father(v)=0,Mark(v)=0,Scan(v)=0,dfn(v)=0,edge(e)=02.r=1 mark(1)=1 dfn(1)=1,v=13.任選未查邊4.標(biāo)記已查edge()=1 因mark(2)=0

6、,故i=2,mark(2)=1, dfn(2)=2,father(2)=1,v=2,Tree= 回到33.任選未查邊4.標(biāo)記已查edge()=1.123456789131110123.任選未查邊4.標(biāo)記已查edge()=1 因mark(2)=0,故i=2,Tree=,mark(2)=1, dfn(2)=2,father(2)=1,v=2 回到33.任選未查邊4.標(biāo)記已查edge()=1. 因mark(3)=0,故i=3,mark(3)=1,Dfn(3)=3,father(3)=2,v=3,Tree=, 回到33.任選未查邊123456789131110123.任選未查邊4.標(biāo)記已查edge()

7、=1. 因mark(3)=0,故i=3,Tree=,mark(3)=1,Dfn(3)=3,father(3)=2,v=3 回到33.任選未查邊4.標(biāo)記已查edge()=1. 因mark(4)=0,故i=4,Tree=, mark(4)=1,dfn(4)=4,father(4)=3,v=4 回到33.以4為起點(diǎn)都已查,scan(4)=1，轉(zhuǎn)5 123456789131110124.標(biāo)記已查edge()=1. 因mark(4)=0,故i=4,Tree=, mark(4)=1,dfn(4)=4,father(4)=3,v=4 回到33.以4為起點(diǎn)都已查,scan(4)=1，轉(zhuǎn)55.father(4)

8、=30,則v=father(4)=3,轉(zhuǎn)3。3.任選未查邊,轉(zhuǎn)4。4.標(biāo)記邊已查edge()=1, 因mark(5)=0,故i=5,Tree=, mark(5)=1,dfn(5)=5,father(5)=3,v=5 轉(zhuǎn)3.123456789131110125.father(4)=30,則v=father(4)=3,轉(zhuǎn)3。3.任選未查邊,轉(zhuǎn)4。4.標(biāo)記邊已查edge()=1, 因mark(5)=0,故i=5,Tree=, mark(5)=1,dfn(5)=5,father(5)=3,v=5 轉(zhuǎn)3.3.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1, 因mark(2)=1,dfn(2)dfn(5),

9、scan(2)=0, 故back=,回到3.123456789131110123.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1, 因mark(2)=1,dfn(2)dfn(5),scan(2)=0, 故back=,回到3.3.以v=5為始點(diǎn)的邊都已查,scan(5)=1,轉(zhuǎn)5.5.father(5)=30,則v=father(5)=3,轉(zhuǎn)3.3.以v=3為始點(diǎn)的邊都已查,scan(3)=1,轉(zhuǎn)55.father(3)=20,則v=father(3)=2,轉(zhuǎn)33.任選未查邊,轉(zhuǎn)4.123456789131110125.father(3)=20,則v=father(3)=2,轉(zhuǎn)33.任選未查邊,轉(zhuǎn)

10、4.4.標(biāo)記邊已查edge()=1.因mark(6)=0則i=6,mark(6)=1,dfn(6)=i=6, father(6)=2, Tree=,v=6 轉(zhuǎn)33.任選未查邊,轉(zhuǎn)44.標(biāo)記邊已查edge()=1. 因mark(7)=0,故i=7,mark(7)=1,dfn(7)=7,father(7)=6,Tree=,v=7 轉(zhuǎn)3123456789131110124.標(biāo)記邊已查edge()=1. 因mark(7)=0,故i=7,mark(7)=1,dfn(7)=7,father(7)=6,Tree=,v=6 轉(zhuǎn)33.以7為起點(diǎn)邊都已查完,故scan(7)=1,轉(zhuǎn)5.5.father(7)=60

11、,故v=father(7)=6,轉(zhuǎn)33.任選未查邊,轉(zhuǎn)44.標(biāo)記已查,因mark(4)=1,dfn(4)dfn(6),scan(4)=1,故Cross=,轉(zhuǎn)3123456789131110124.標(biāo)記已查,因mark(4)=1,dfn(4)dfn(6),scan(4)=1,故Cross=,轉(zhuǎn)33.以v=6為起點(diǎn)的邊都已查完,故scan(6)=1,轉(zhuǎn)5.5.father(6)=20,故v=father(6)=2,轉(zhuǎn)33.以v=2為起點(diǎn)的邊都已查完,故scan(2)=1,轉(zhuǎn)55.father(2)=10,故v=father(2)=1,轉(zhuǎn)3123456789131110125.father(2)=1

12、0,故v=father(2)=1,轉(zhuǎn)33.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1, 因mark(4)=1, DFN(4)DFN(1),故Forward=,回到3.3.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1,因mark(7)=1, DFN(7)DFN(1),故Forward=,回到3.3.因以1為起點(diǎn)的邊都已查完,故scan(1)=1,轉(zhuǎn)55.因father(1)=0為根,轉(zhuǎn)6123456789131110125.因father(1)=0為根,轉(zhuǎn)66.因?yàn)橛行┙Y(jié)點(diǎn)未訪問,故i=8,轉(zhuǎn)22.選滿足mark(r)=0的點(diǎn)r=8,mark(8)=1,dfn(8)=8,v=83.任選未查邊,

13、轉(zhuǎn)44.標(biāo)記已查edge()=1,因mark(9)=0,故i=9mark(9)=1,dfn(9)=9,father(9)=8, v=9Tree=, 轉(zhuǎn)33.任選未查邊,轉(zhuǎn)4.4.標(biāo)記已查edge()=1,因mark(10)=0,故123456789131110124.標(biāo)記已查edge()=1,因mark(10)=0,故 i=10,mark(10)=1,dfn(10)=10,father(10)=9, v=10Tree=, 轉(zhuǎn)33.任選未查邊,轉(zhuǎn)4.4.標(biāo)記已查edge()=1,因mark(11)=0,故i=11,mark(11)=1,dfn(11)=11,father(11)=10,v=11T

14、ree=, 轉(zhuǎn)3123456789131110124.標(biāo)記已查edge()=1,因mark(11)=0,故i=11,mark(11)=1,dfn(11)=11,father(11)=10,v=11Tree=, 轉(zhuǎn)33.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1,因mark(6)=1, dfn(6)dfn(11),scan(6)=1,故Cross=,回到3.3.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1,因mark(9)=1123456789131110123.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1,因mark(9)=1, dfn(9)dfn(11),scan(9)=0,故back=,

15、轉(zhuǎn)33.以v=11為起點(diǎn)的邊都已查完,scan(11)=1,轉(zhuǎn)55.father(11)=100,故v=father(11)=10,轉(zhuǎn)3.3.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1,因mark(12)=0故i=12,mark(12)=1,dfn(12)=12,father(12)=10,v=12Tree=, 轉(zhuǎn)3123456789131110124.標(biāo)記已查edge()=1,因mark(12)=0故i=12,mark(12)=1,dfn(12)=12,father(12)=10,v=12Tree=, 轉(zhuǎn)33.以v=12為起點(diǎn)邊都已查完,scan(12)=1,轉(zhuǎn)55.因father(12)

16、=100,故v=father(12)=10,轉(zhuǎn)33.因v=10為起點(diǎn)邊都已查完,scan(10)=1,轉(zhuǎn)55.因father(10)=90,故v=father(10)=9,轉(zhuǎn)33.任選未查邊,轉(zhuǎn)4123456789131110123.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1,因mark(12)=1,dfn(12)dfn(9),則forward=,回33.以9為始點(diǎn)邊都已查完,scan(9)=1,轉(zhuǎn)55.因father(9)=80,故v=father(9)=8,轉(zhuǎn)3.3.以8為始點(diǎn)邊都已查完,scan(8)=1,轉(zhuǎn)55.因father(8)=0,轉(zhuǎn)66.因?yàn)橛悬c(diǎn)未訪問,故i=i+1,轉(zhuǎn)22.

17、選滿足mark(r)=0的點(diǎn)v=13,mark(13)=1,dfn(13)=13123456789131110126.因?yàn)橛悬c(diǎn)未訪問,故i=i+1,轉(zhuǎn)22.選滿足mark(r)=0的點(diǎn)v=13,mark(13)=1,dfn(13)=133.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1,因mark(8)=1, dfn(8)dfn(13),scan(8)=1,cross=,轉(zhuǎn)33.任選查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1,因mark(9)=1, dfn(9)dfn(13),scan(9)=1,cross=,轉(zhuǎn)3123456789131110123.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1,因

18、mark(9)=1, dfn(9)dfn(13),scan(9)=1,cross=,轉(zhuǎn)33.任選未查邊,轉(zhuǎn)44.標(biāo)記已查edge()=1,因mark(12)=1, dfn(12)dfn(13),scan(12)=1,cross=,轉(zhuǎn)33.因以13為始邊已查,scan(13)=1,轉(zhuǎn)55.因father(13)=0,轉(zhuǎn)66.因所有點(diǎn)mark(v)=1,故結(jié)束. 3個(gè)根即3棵樹,紅實(shí)邊為樹,粗虛為向前邊,細(xì)虛為回退,黑線為橫跨邊12345678913111012 從如下的DFS過程可知,原圖是弱連通(看成無向圖時(shí)連通)時(shí),DFS是不連通的. 定理6.6.1 強(qiáng)連通圖的DFS林是連通的.證明:假設(shè)D

19、FS林不連通,則至少有2棵子樹T1,T2.設(shè)r1,r2是其根,r1r2,T1先于T2得到. 由深度優(yōu)先算法的特點(diǎn)可知,不存在起點(diǎn)在T1,終點(diǎn)在T2的邊. 故從r1不能到達(dá)T2的各結(jié)點(diǎn),故不是強(qiáng)連通的! 矛盾,故假設(shè)錯(cuò).12345678910111213 從如下的DFS過程可知,原圖是弱連通(看成無向圖時(shí)連通)時(shí),DFS是不連通的. 定理6.6.1 強(qiáng)連通圖的DFS林是連通的. 定義6.6.1 有向圖G極大的強(qiáng)連通子圖稱為它的強(qiáng)連通分量,或強(qiáng)連通塊. 推論6.6.1 對(duì)于G的強(qiáng)連通分量的DFS子樹是連通的. 設(shè)G1=(V1,E1),G2=(V2,E2).,Gk=(Vk,Ek)是G的強(qiáng)連通塊。 T

20、是G的DFS樹，T1,T2,.,Tk是對(duì)應(yīng)強(qiáng)連通塊的子樹。 r1,r2,rk是這些子樹的根！ 確定強(qiáng)連通塊Gi的根ri是算法的關(guān)鍵. 為此分析G中諸邊間的關(guān)系. 確定強(qiáng)連通塊Gi的根ri是算法的關(guān)鍵.。 (1)若vVi, wVj,ij, 則邊不可能是回退邊,由回退邊的定義可知,始點(diǎn)在Vi的回退邊，終點(diǎn)在同一個(gè)強(qiáng)連通塊Vi中。如下中細(xì)虛線。 (2) 若vVi, wVj,ij,rj是ri的祖先，則邊不可能是橫跨邊, 不是直系才能同跨。只能是： (2.1)rj在ri的左邊.下圖右邊是Vi,左邊Vj ,右 (2.2) vVi, wVi,同一個(gè)子樹中，左， 無向圖分塊是low(v)dfn(father(

21、v)成立,求Low() 有向圖分塊是lowLink(v)=dfn(v)成立，求LowLink()1234567891011121312345678913111012 確定強(qiáng)連通塊Gi的根ri是算法的關(guān)鍵.。 (1)沒有類型的回退邊,其中vVi, wVj,ij,始點(diǎn)在Vi的回邊，終點(diǎn)同在Vi中。 (2)沒有類型的橫跨邊,其中vVi, wVj,ij,rj是ri的祖先。只能是： (2.1)rj在ri的左邊.下圖右邊是Vi,左邊Vj , (2.2) vVi, wVi,同一個(gè)子樹中， 無向圖分塊是low(v)dfn(father(v)成立 有向圖分塊也需類似lowLink()函數(shù)。12345678913

22、111012rjrivw 定義6.6.2 LowLink(v)=min(dfn(v),dfn(w)|v的子孫到w有回退邊或橫跨邊,v與w屬同一個(gè)強(qiáng)連通塊 ) v=5時(shí)w=3,5(v)的子孫4到3(w)有回退邊! 定理6.6.2:v是有向圖G的強(qiáng)連通分支的根 LowLink(v)=dfn(v) LowLink(v)的算法： 1.首次訪問v時(shí),LowLink(v)=dfn(v); 2.若有回退邊被查, 如v=4,w=3時(shí) LowLink(v)=min(LowLink(v),dfn(w); (1) 3.若有橫跨邊且v,w同塊,公式見(1),如v=5,w=4時(shí) 4.當(dāng)v的兒子s完全掃描后返回v時(shí) Lo

23、wLink(v)=min(LowLink(v),lowLink(s); 12345678910111213LowLink(v)的算法： 1.首次訪問v時(shí),LowLink(v)=dfn(v); 2.若有回退邊被查, LowLink(v)=min(LowLink(v),dfn(w); (1) 3.若有橫跨邊且v,w屬同連通塊,公式如(1); 4.當(dāng)v的兒子s完全掃描后返回v時(shí) LowLink(v)=min(LowLink(v),lowLink(s); LowLink(4)=dfn(4)=4,LowLink(4)=min(LowLink(4),dfn(3)=min(4,3)=3;反向邊LowLink

24、(3)=min(lowlink(3),linklow(4)=3LowLink(5)=dfn(5)=5LowLink(5)=min(lowLink(5),dfn(4)=4 橫跨邊12345678910111213LowLink(v)的算法： 1.首次訪問v時(shí),LowLink(v)=dfn(v); 2.若有回退邊被查, LowLink(v)=min(LowLink(v),dfn(w); (1) 3.若有橫跨邊(v,w)且v,w屬同連通塊,公式如(1); 4.當(dāng)v的兒子s完全掃描后返回v時(shí) 為了判斷橫跨邊屬同一塊，需建立stack數(shù)組,按DFS的訪問次序?qū)⒔Y(jié)點(diǎn)存入,可確定強(qiáng)連通塊包含的結(jié)點(diǎn),可判斷v

25、與w是否同塊。 無向圖stack是邊集,有向圖是點(diǎn)集 一旦得到一個(gè)塊，則將該塊的結(jié)點(diǎn)從stack中移出。 添point數(shù)組，若v在stack中則point(v)=1,否則為0。123456789101112131.stack=,i=1,Father(v)=0,Mark(v)=0,point(v)=0,edge(e)=02.任選滿足Mark(r)=0的結(jié)點(diǎn)r,置其 DFN(r)=i, Mark(r)=1, LowLink(r)=1,stack1=r,point(r)=1,v=r3.若以v起點(diǎn)的邊都已查轉(zhuǎn)5,否則任選未查邊(v,w)轉(zhuǎn)44.邊(v,w)標(biāo)為已查Edge(v,w)=1,執(zhí)行以下操作后

26、回到3 4.1若Mark(w)=0 則 i=i+1, DFN(w)=i, LowLink(w)=i, Mark(w)=1, father(w)=v,stack+=w, point(w)=1,v=w 4.2 若Mark(w)=1,DFN(w)DFN(v),point(w)=1(w與v同塊) 則LowLink(v)=min(LowLink(v),dfn(w) 5. 若LowLink(v)=dfn(v)則構(gòu)成塊,移去stack的棧頂?shù)絭的結(jié)點(diǎn),重新置其point(x)=0。 若father(v)=0轉(zhuǎn)6，否則LowLink(father(v)=min(LowLink(father(v),LowLin

27、k(v),v=fahter(v)轉(zhuǎn)3 6.若所有結(jié)點(diǎn)Mark(x)=1結(jié)束,否則轉(zhuǎn)2 1.stack=,i=1,Father(v)=0,Mark(v)=0,point(v)=0 2.DFN(1)=1, Mark(1)=1, LowLink(1)=1, stack=1, point(1)=1,v=r 3.任選未查邊,轉(zhuǎn)4 4.標(biāo)示已查,因mark(2)=0,i=2,dfn(2)=2, mark(2)=1, LowLink(2)=2,stack=1,2,point(2)=1,father(2)=1,v=2,轉(zhuǎn)3 3.任選，轉(zhuǎn)4 4.標(biāo)示已查,因mark(3)=0,i=3,dfn(3)=3,mark

28、(3)=1,LowLink(3)=3,stack=1,2,3,point(3)=1,fath(3)=2,v=3,轉(zhuǎn)3 3. 任選,轉(zhuǎn)4 4.標(biāo)示已查,因mark(4)=0,i=4,dfn(4)=4,mark(4)=1,LowLink(4)=4,stack=1,2,3,4,point(4)=1,fath(4)=3,v=4,轉(zhuǎn)412345678910111213 4.標(biāo)示已查,因mark(4)=0,i=4,dfn(4)=4,mark(4)=1,LowLink(4)=4,stack=1,2,3,4,point(4)=1,fath(4)=3,v=4,轉(zhuǎn)3 3.任選，轉(zhuǎn)4 4.標(biāo)示已查,因mark(3)

29、=1,dfn(3)dfn(4),point(3)=1LowLink(4)=min(LowLink(4),dfn(3)=3(回退邊),轉(zhuǎn)3 3.因4為起點(diǎn)的邊都已查，轉(zhuǎn)5 5.因LowLink(4)dfn(4)故不構(gòu)成塊, 又因father(4)=30,故 lowLink(father(4)=min(lowLink(3),lowLink(4)=3,v=3轉(zhuǎn)3 3.任選,轉(zhuǎn)4 4.標(biāo)示已查,因mark(5)=0,i=5,dfn(5)=5,mark(5)=1, LowLink(5)=5,stack=1,2,3,4,5,point(5)=1,fath(5)=3,v=512345678910111213

30、4.標(biāo)示已查,因mark(5)=0,i=5,dfn(5)=5,mark(5)=1, LowLink(5)=5,stack=1,2,3,4,5,point(5)=1,fath(5)=3,v=53.任選未查邊,轉(zhuǎn)44.標(biāo)示已查,因mark(4)=1,dfn(4)dfn(5),point(4)=1,lowLink(5)=min(lowLink(5), dfn(4)=4(橫跨邊),轉(zhuǎn)33.因以5為起點(diǎn)邊已查，轉(zhuǎn)54.因lowLink(5)dfn(5)故不是塊 又因father(5)=30,故 lowLink(3)=min(LowLink(3),LowLink(5)=3 v=father(5)=3 轉(zhuǎn)3

31、3.因以3為起點(diǎn)邊已查,轉(zhuǎn)55.因lowLink(3)=dfn(3)=3故為塊！棧頂?shù)?所有點(diǎn)3,4,512345678910111213 stack=1,2,3,4,55.因lowLink(3)=dfn(3)=3故為塊！棧頂?shù)?所有點(diǎn)3,4,5,Point(3)=point(4)=point(5)=0. 又因father(3)=20，故可回溯 lowLink(2)=min(LowLink(2),LowLink(3)=2, v=father(3)=2,轉(zhuǎn)33.任選未查邊，轉(zhuǎn)44.標(biāo)示已查,因mark(6)=0,故i=6,dfn(6)=6,mark(6)=1,Father(6)=2,lowLin

32、k(6)=6,point(6)=1,stack=1,2,6,v=63.任選未查邊,轉(zhuǎn)44.標(biāo)示已查,因mark(7)=0,故i=7,dfn(7)=7,mark(7)=1,Father(7)=6,lowLink(7)=7,point(7)=1,stack=1,2,6,7,v=7123456789101112134.標(biāo)示已查,因mark(7)=0,故i=7,dfn(7)=7,mark(7)=1,Father(7)=6,lowLink(7)=7,point(7)=1,stack=1,2,6,7,v=73.任選未查邊,轉(zhuǎn)44.標(biāo)示已查,因mark(6)=1,dfn(6)dfn(7),point(6)=

33、1,lowLink(7)=min(LowLink(7),dfn(6)=6(回退邊) 3.任選示查邊,轉(zhuǎn)44.標(biāo)示已查,因mark(8)=0,故i=8,dfn(8)=8,mark(8)=1,fath(8)=6,lowLink(8)=8,point(8)=1,stack=1,2,6,7,8,v=83.任選未查邊,轉(zhuǎn)44.標(biāo)示已查,因mark(9)=0,故i=9,dfn(9)=9,mark(9)=1,fath(9)=8,lowLink(9)=9,point(9)=1,stack=1,2,6,7,8,9,v=93.任選未查邊,轉(zhuǎn)4123456789101112134.標(biāo)示已查,因mark(9)=0,故

34、i=9,dfn(9)=9,mark(9)=1,fath(9)=8,lowLink(9)=9,point(9)=1,stack=1,2,6,7,8,9,v=93.任選未查邊,轉(zhuǎn)44.標(biāo)示已查,因mark(7)=1,dfn(7)dfn(9),point(7)=1故lowLink(9)=min(lowLink(9),dfn(7)=7,轉(zhuǎn)33.因以9為起點(diǎn)邊全查完,轉(zhuǎn)55.lowLink(9)dfn(9),故不是塊 又因father(9)=8 0不是根,故 lowLink(8)=min(LowLink(8),LowLink(9)=7,v=8 轉(zhuǎn)33.任選未查邊,轉(zhuǎn)44.標(biāo)示已查,因mark(10)=0

35、,故i=10,dfn(10)=10, mark(10)=1,fath(10)=8, lowLink(10)=10, point(10)=1, stack=1,2,6,7,8,9,10,v=10,轉(zhuǎn)3.123456789101112134.標(biāo)示已查,因mark(10)=0,故i=10,dfn(10)=10, mark(10)=1,fath(10)=8, lowLink(10)=10, point(10)=1, stack=1,2,6,7,8,9,10,v=10,轉(zhuǎn)3.3.任選轉(zhuǎn)44.標(biāo)示已查,因mark(9)=1,dfn(9)dfn(10),point(9)=1,故lowLink(10)=min

36、(LowLink(10),dfn(9)=9(橫跨邊),轉(zhuǎn)33.因以10為起點(diǎn)邊全查完,轉(zhuǎn)55.因lowLink(10)dfn(10)故不是塊.又因father(10)=8 0,不是根,可回溯.lowLink(8)=min(LowLink(8),lowLink(10)=7 v=83.因以8為起點(diǎn)邊全查完,轉(zhuǎn)5123456789101112133.因以8為起點(diǎn)邊全查完,轉(zhuǎn)55.因lowLink(8)dfn(8)故不是塊.又因father(8)=6 0,不是根,可回溯.lowLink(6)=min(LowLink(6),lowLink(8)=6 v=6轉(zhuǎn)33.因以6為起點(diǎn)邊全查完,轉(zhuǎn)5 stack=1,2,6,7,8,9,105.因lowLink(6)=dfn(6)故是塊.棧頂?shù)?的6,7,8,9,10是塊Point(6)point(10)=0, stack=1,2又因father(6)=2 0,不是根,可回溯.lowLink(2)=min(LowLink(2),lowLink(2)=2 v=2轉(zhuǎn)33.因以2為起點(diǎn)邊全查完,轉(zhuǎn)5 5.因lowLink(2)=dfn(2)故是塊.棧頂?shù)?2是塊poin