圖的遍歷算法課件

第三部分最先割技術(shù)

第九章圖的遍歷

第三部分最先割技術(shù)1第九章圖的遍歷9．1引言9．2深度優(yōu)先搜索9．3深度優(yōu)先搜索的應用9．4廣度優(yōu)先搜索9．5廣度優(yōu)先搜索的應用第九章圖的遍歷2在一些諸如找出最短路徑和最小生成樹的圖的算法中，用由它們相應的算法順序訪問頂點和邊。然而，在一些其他算法中，訪問頂點的順序是不重要的，重要的是，不管輸入的圖如何，用一種系統(tǒng)的順序來訪問頂點。在本章中，我們討論圖遍歷的兩種方法：深度優(yōu)先搜索和廣度優(yōu)先搜索。9.1引言在一些諸如找出最短路徑和最小生成樹的圖的算法中，用由它3設G=(V,E)是一個有向或無向圖，G的深度優(yōu)先搜索運作如下：1、初始化所有的頂點訪問標志為未訪問；2、任意選擇一個起始頂點，比如說s∈V，并標上已訪問。3、從s的鄰接頂點中選擇任意一個頂點w，訪問該頂點，同時將其標志為被訪問。9.2深度優(yōu)先搜索設G=(V,E)是一個有向或無向圖，G的深度優(yōu)4

3、將訪問指針移至w結(jié)點，將其標志為被訪問，然后從w的臨接結(jié)點中選擇一個未被訪問的結(jié)點，向前繼續(xù)訪問；

4、在訪問過程中，按照上述的深度優(yōu)先的方式向前推進，一旦發(fā)現(xiàn)某一個頂點X的所有鄰接點都被標志為已訪問，訪問指針回退至上一層，繼續(xù)訪問該層沒有被訪問的其他的子節(jié)點。

5、如此往復，直至回退到根節(jié)點為止。3、將訪問指針移至w結(jié)點，將其標志為被訪問，5算法9.1DFSInput:有向或無向圖G=(V,E)。Output:在相應的深度優(yōu)先搜索樹中對頂點的前序和后序。1.predfn0;postdfn02.For每個頂點v∈V3.標記v未訪問//初始化訪問標志4.Endfor5.For每個頂點v∈V6.Ifv未訪問thendfs(v)//調(diào)用訪問7.Endfor算法9.1DFS6過程dfs(v)//遞歸訪問1.標記v已訪問2.predfnpredfn+1

//進來訪問，是前序號3.For每條邊(v,w)∈E4.Ifw標記為未訪問thendfs(w)5.Endfor6.postdfnpostdfn+1

//結(jié)點被訪問完畢，退回時訪問該語句，即后序號算法生成結(jié)構(gòu)：1、樹（全部頂點相連，能夠一次到達）；2、森林（頂點不相連，不能夠一次都到達）。過程dfs(v)//遞歸訪問71、無向圖的情況分析設G=(V,E)是無向圖，作為遍歷的結(jié)果，G的邊分成一下兩種類型。樹邊：深度優(yōu)先搜索樹中的邊，如果在搜索邊(v,w)時，w是首次被訪問，則邊(v,w)是樹邊?；剡叄核衅渌倪?。例9.1。1、無向圖的情況分析8edcbfahgijedcbfahgij9abcdefghij1,102,93,34,25,16,87,78,69,510,4abcdefghij1,102,93,34,25,16,87102、有向圖的情況

有向圖中的深度優(yōu)先搜索導致結(jié)果：一個或多個(有向)生成樹，樹的多少取決于初始點。（1）選擇某起始點v，深度優(yōu)先搜索一棵樹，它由從v出發(fā)所有可到達的頂點組成。（2）沒有遍歷完所有的頂點，選擇另一個頂點w繼續(xù)（未訪問過頂點），構(gòu)建一顆從w可到達的所有未訪問頂點組成的樹，這個過程繼續(xù)下去直到所有的頂點都被訪問過。（3）重復上述過程，直至所有頂點被訪問完畢。2、有向圖的情況11G的邊分成4種類型：1、樹邊：深度優(yōu)先搜索樹中的邊。如果在搜索邊(v,w)時，w是第一次被訪問，則(v,w)是樹邊。2、回邊：在迄今為止構(gòu)建的深度優(yōu)先搜索樹中，w是v的祖先，并且當搜索(v,w)時頂點w已被標上已訪問，這樣形成的邊(v,w)是回邊。3、前向邊：在迄今為止構(gòu)建的深度優(yōu)先搜索樹中，w是v的后裔，并且當搜索(v,w)時頂點w被標上已訪問，這種形式的邊(v,w)是前向邊。3、橫跨邊：所有其它的邊。見例9.2。G的邊分成4種類型：12cdebafcdebaf13abefcdafebcd1,42,33,14,25,66,51,42,23,14,35,66,5abefcdafebcd1,42,33,14,25,66,514

(1)頂點v被訪問標記為訪問的過程，每一個頂點的調(diào)用耗費是(1)。一共需要n個頂點，所以該過程的總耗費是(n)。（2）算法的步驟1和步驟3分別耗費(1)和(n)時間。//初始化序列號、訪問標志（3）步驟6測試一個頂點是否已標記要耗費(n)。（注意：測試方法是要依次搜索該點的鄰接點，看是否從某個點訪問過它，所以是(n)）

9.2.1深度優(yōu)先搜索的時間復雜性(1)頂點v被訪問標記為訪問的過程，每一個頂點的調(diào)用15（4）測試頂點w是否標記為未訪問，這一步的執(zhí)行次數(shù)等于頂點v的鄰接點數(shù)。

這一步執(zhí)行的總次數(shù)，在有向圖的情況下等于它的邊數(shù)，在無向圖的情況下是邊數(shù)的兩倍。于是，不論是有向圖還是無向圖，這一步的耗費是(m)，（5）算法的總運行時間是：(m+n)。如果圖是連通的或有m≥n,則運行時間簡單地為(m)。但是必須強調(diào)的是，圖假設是用鄰接表表示的。（4）測試頂點w是否標記為未訪問，這一步的執(zhí)行次數(shù)等于169.3深度優(yōu)先搜索的應用

深度優(yōu)先搜索在圖和幾何算法中用得很普遍。在本節(jié)中，我們列舉它的一些重要應用。設G=(V,E)是一個有n個頂點和m條邊的有向或無向圖。為了測試G是否至少有一個回路，我們對G用深度優(yōu)先搜索，如果在搜索過程中探測到一條回邊，那么G是有回路的，否則G是無回路的。

注意G可能不連通，如果G是連通無向圖，那么不需要對圖進行遍歷，因為G是無回路的當且僅當它是一棵樹，則當且僅當m=n-1。9.3.1圖的無回路性9.3深度優(yōu)先搜索的應用設G=(V,E)是一個17給出一個有向無回路圖(dag)G=(V,E)，拓撲排序問題是找出圖頂點的一個線性序列，使得如果(v,w)∈E，那么在這個序中v在w前出現(xiàn)。例如，在圖9.3(a)中所示的有向無回路圖中，頂點的一個可能的拓撲排序是a,b,d,c,e,f,g。我們將假設在這種有向無回路圖中有一個入度是0的唯一的頂點s，如果不是的話，我們可以簡單地添一個新的頂點s，然后讓s到所有入度為0的點加上邊。9.3.2拓撲排序給出一個有向無回路圖(dag)G=(V,E)，拓18abdfcegsabdfcegs19接下來，我們從頂點s起，簡單地對圖G執(zhí)行深度優(yōu)先搜索。當遍歷完成時，計數(shù)器postdfn定義了一個在有向無回路圖中頂點的反撲排序，于是，為了得到這個拓撲序，可以在算法DFS中在計數(shù)器postdfn剛好被增加后，加上一個輸出步，把輸出結(jié)果翻轉(zhuǎn)過來就是我們需要的拓撲序。接下來，我們從頂點s起，簡單地對圖G執(zhí)行深度優(yōu)先20

關(guān)節(jié)點:

在多于兩個頂點的無向圖G中，存在一個頂點v，如果有不同于v的兩個頂點u和w，在u和w間的任何路徑都必定經(jīng)過頂點v。這樣，如果G是連通的，移去v和與它關(guān)聯(lián)的邊，將產(chǎn)生G的非連通子圖（森林）。一個圖如果是連通的并且沒有關(guān)節(jié)點則稱為是雙連通的。9.3.3尋找圖的關(guān)節(jié)點關(guān)節(jié)點:9.3.3尋找圖的關(guān)節(jié)點21由深度優(yōu)先生成樹的特性可以得到如下結(jié)論：1、根是一個關(guān)節(jié)點當且僅當在深度優(yōu)先搜索樹中，它有兩個或更多的兒子；原因：圖中不存在連接不同子樹頂點的邊，刪掉根結(jié)點后，生成樹就變成了森林。2、根以外的其他結(jié)點V，如果其某棵子樹的根和子樹中的其他結(jié)點均沒有指向該結(jié)點v的祖先的回邊?；蛘撸焊酝獾捻旤cv是一個關(guān)節(jié)點當且僅當v有一個兒子w，使得β(w)≥α(v)。由深度優(yōu)先生成樹的特性可以得到如下結(jié)論：22為了找出關(guān)節(jié)點的集合，在圖G上執(zhí)行一個深度優(yōu)先搜索遍歷。在遍歷的過程中，對每個頂點v保持兩個標號：α(v)和β(v)，α(v)只是深度優(yōu)先搜索算法中的predfn，每次調(diào)用深度優(yōu)先搜索過程，就加1，β(v)初始化為α(v)，但在后來的遍歷過程中可以改變。對于每一個訪問的頂點，令β(v)是下面幾個中的最小值。

α(v)；//葉子結(jié)點α(u)，對于每個頂點u,(v,u)是回邊；β(w)，在深度優(yōu)先搜索樹中的每條邊(v,w)。為了找出關(guān)節(jié)點的集合，在圖G上執(zhí)行一個深度23上述β(v)值的變化是：一旦某個點出現(xiàn)回邊，則該結(jié)點的β(v)值必然變小為其祖先結(jié)點k的β()值。如果某個結(jié)點的β值大于其α值，則肯定有一個子結(jié)點，必然是關(guān)節(jié)點；如果該值小于其α值，肯定是有回邊了。如果等于α值，則肯定是沒有孩子了。

使用這個值的目的就是在回訪結(jié)點的過程中，通過判斷結(jié)點的α與β值的關(guān)系以得到該結(jié)點是什么結(jié)點

上述β(v)值的變化是：一旦某個點出現(xiàn)回邊，則24算法9.2ARTICPOINTSINPUT:連通無向圖G=(V,E)。OUTPUT:包含G的所有可能關(guān)節(jié)點的數(shù)組A[1…n]。1.設s為起始頂點2.for每個頂點v∈V3.標記v未訪問4.endfor//初始化全部結(jié)點為沒有訪問5.predfn0;count0;rootdegree06.dfs(s)//從初始結(jié)點開始訪問算法9.2ARTICPOINTS25過程dfs(v)1.標記v已訪問；artpointfalse;//關(guān)節(jié)點標記predfnpredfn+1//標記序號2.α(v)predfn;

β(v)predfn//初始化訪問序號3.For每條邊(v,w)∈E4.If(v,w)為樹邊then5.dfs(w)//深入開始訪問后續(xù)結(jié)點6.Ifv=sthen

//樹根結(jié)點7.rootdegreerootdegree+18.Ifrootdegree=2thenartpointtrue//根節(jié)點至少存在兩個子樹，是關(guān)節(jié)結(jié)點9.Else

過程dfs(v)26

10.β(v)min{β(v),β(w)}11.Ifβ(w)≥α(v)thenartpointtrue//有孩子就標記為關(guān)節(jié)結(jié)點12.Endif13.Elseif(v,w)是回邊then//v!=s

β(v)min{β(v),α(w)}14.Elsedonothing{w是v的父親}15.Endif16.Endfor17.Ifartpointthen18.countcount+119.A[count]

v20.Endif10.β(v)min{β(27（1）首先，算法執(zhí)行必要的初始化，特別地，count是關(guān)節(jié)點的個數(shù)，rootdegree是深度優(yōu)先搜索樹根的度，這在后來決定根是否是關(guān)節(jié)點時是需要的。（2）接著深度優(yōu)先搜索從根開始著手，對于每一個訪問的頂點v，α(v)和β(v)用predfn來初始化。（3）在搜索從某頂點w退回到v時，要做兩件事，首先，如果發(fā)現(xiàn)β(w)比β(v)小，β(v)被設置為β(w)，其次，如果β(w)≥α(v)，那么這就指出v是一個關(guān)節(jié)點，因為從w到v的祖先頂點必須經(jīng)過v。（1）首先，算法執(zhí)行必要的初始化，特別地，28這說明在圖9.4種，可以看到，從以w為根的子樹到u的任何路徑必定包括v，因此v是一個關(guān)節(jié)點。以w為根的子樹包含一個或多個連通分支。在這個圖中，根u是關(guān)節(jié)點，因為它的度大于1。見例9.3。這說明在圖9.4種，可以看到，從以w為根的子樹到u的29edcbfahgijedcbfahgij30abcdefghij1,12,13,34,35,36,17,18,89,810,8abcdefghij1,12,13,34,35,36,17,31（1）初始化各個頂點；（2）從a-e開始搜索，一直到e均是正常搜索，各個數(shù)值依次遞增增長；（3）搜索到e時，找到一個回邊(e,c)，則e的β(e)=min{a[c]=3；a[e]=5,β[c]=3}=3；（4）回退至d點時，該點的β[d]=3;(原來是4);(5)回退到c點，β[c]=3，由于β[d]>=a[c]，所以該結(jié)點是關(guān)節(jié)點。(6)回退到b結(jié)點，β[c]>=a[b]，所以b也是一個關(guān)節(jié)點。此時，發(fā)現(xiàn)b結(jié)點還有一個分支，繼續(xù)搜索該分支。（1）初始化各個頂點；32（1）探測到（j,h）是一個回邊，所以將

β[j]=a[h]=8；（2）回到i點，該點的β[i]也被改為8；（3）同理，對于h點來講，其β[h]也被置為8；此時，由于β[i]>a[h],所以h是關(guān)節(jié)點；（4）回退到g點,同樣存在β[h]>a[g]，所以該點也是關(guān)節(jié)點；檢測到該點存在回路，所以將其β[g]值置為其祖先結(jié)點的值=1；（5）β[f]β[b]也被置為1,搜索回到a結(jié)點，因為a結(jié)點只有一個分支孩子，所以a不是關(guān)節(jié)點

（1）探測到（j,h）是一個回邊，所以將33edcbfahgijedcbfahgij34abcdefghij1,12,13,34,35,36,17,18,79,710,7abcdefghij1,12,13,34,35,36,17,35給出一個有向圖G=(V,E)，G中的強連通分支是它頂點的極大集，在該集中，每一對頂點間都存在一條路徑。下面的算STRONGCONNECTCOMP用深度優(yōu)先搜索來確定在有向圖中的所有的強連通分支。9.3.4強連通分支給出一個有向圖G=(V,E)，G中的強連通分支是36算法9.3STRONGCONNECTCOMPINPUT:有向圖G=(V,E)OUTPUT:G中的強連通分支1.在圖G上執(zhí)行深度優(yōu)先搜索，對每一個頂點賦給相應的postdfn值。2.顛倒圖G中邊的方向，構(gòu)成一個新的圖3.從具有最大postdfn數(shù)值的頂點開始，在上執(zhí)行深度優(yōu)先搜索，如果深度優(yōu)先搜索不能到達所有的頂點，則在余下的頂點中找出一個postdfn數(shù)值最大的頂點，開始下一次深度優(yōu)先搜索。

4.在最終得到的森林中的每一棵樹對應一個強連通分支。見例9.4。算法9.3STRONGCONNECTCOMP37cdebaf原圖cdebaf原圖38abefcdafebcd1,42,33,14,25,66,51,42,23,14,35,66,5深度優(yōu)先搜索結(jié)果圖abefcdafebcd1,42,33,14,25,66,539cdeafb將原圖翻轉(zhuǎn)圖cdeafb將原圖翻轉(zhuǎn)圖40adecbf最后的結(jié)果adecbf最后的結(jié)果411、在廣度優(yōu)先搜索中，當訪問了一個頂點v后，接下來訪問鄰接于v的所有頂點，產(chǎn)生出來的樹稱為廣度優(yōu)先搜索樹。2、這種遍歷的方法可以通過用一個隊列存儲沒有檢查過的頂點來實現(xiàn)（先進先出）。3、廣度優(yōu)先的算法BFS能夠用到有向和無向圖中。初始的時候，所有的頂點都標上未訪問，計數(shù)器bfn初始為0，它表示頂點從隊列中移出的序。在無向圖的情況下，一條邊或者是樹邊或者是橫跨邊；如果圖是有向的，那么邊可以是樹邊、回邊或橫跨邊，不存在前向邊。9.4廣度優(yōu)先搜索1、在廣度優(yōu)先搜索中，當訪問了一個頂點v后，接下42算法9.1BFSInput:有向或無向圖G=(V,E)。Output:廣度優(yōu)先搜索次序中頂點的編號。1.bfn02.For每個頂點v∈V3.標記v未訪問4.Endfor5.For每個頂點v∈V6.Ifv未訪問thenbfs(v)7.Endfor算法9.1BFS43過程bfs(v)1.Q{v}//被訪問頂點進隊列2.標記v已訪問3.WhileQ≠{}4.vPop(Q)

//彈出頭頂點5.bfnbfn+16.For每條邊(v,w)∈E//保證廣度優(yōu)先7.Ifw標記未為訪問then8.Push(w,Q)//壓入隊列9.標記w已訪問10.endif11.Endfor12.Endwhile過程bfs(v)44abgcdefhij12345678910圖9.1的廣度優(yōu)先搜索abgcdefhij12345678910圖9.1的廣度優(yōu)先45時間復雜性廣度優(yōu)先搜索應用在具有n個頂點m條邊的圖(包括有向圖和無向圖)上時，它的時間復雜性是和深度優(yōu)先搜索一樣的，為(m+n)。如果圖是連通的或者m≥n，那么時間復雜性可簡化為(m)。第九章-圖的遍歷算法課件46設G=(V,E)是連通無向圖，s是V中的一個頂點，當把算法BFS用到G上并以s作為起始點時，產(chǎn)生的廣度優(yōu)先搜索樹中從s到其他任意頂點的路徑有最少的邊數(shù)。

假如我們要找出從s到其他每一頂點的距離，這里從s到一個頂點v的距離定義為：從s到v的任意路徑的最少邊數(shù)。

于是上面的問題可以很容易做到，我們只要在每個頂點壓入隊列前，標上它的距離就可以了。這樣，起始點將標上0，它的鄰接點是1，以此類推。9.5廣度優(yōu)先搜索的應用設G=(V,E)是連通無向圖，s是V中的一個47很明顯，每個頂點的標號是它到起始點的最短距離。例如在圖9.7中，頂點a將被標上0，頂點b和g標上1，頂點c,f和h標上2，最后，頂點d,e,i和j標上3。注意，這里的頂點編號方式不同于算法中廣度優(yōu)先的編號方式。

很明顯，每個頂點的標號是它到起始點的最短距離。48

謝謝謝謝49第三部分最先割技術(shù)

第九章圖的遍歷

第三部分最先割技術(shù)50第九章圖的遍歷9．1引言9．2深度優(yōu)先搜索9．3深度優(yōu)先搜索的應用9．4廣度優(yōu)先搜索9．5廣度優(yōu)先搜索的應用第九章圖的遍歷51在一些諸如找出最短路徑和最小生成樹的圖的算法中，用由它們相應的算法順序訪問頂點和邊。然而，在一些其他算法中，訪問頂點的順序是不重要的，重要的是，不管輸入的圖如何，用一種系統(tǒng)的順序來訪問頂點。在本章中，我們討論圖遍歷的兩種方法：深度優(yōu)先搜索和廣度優(yōu)先搜索。9.1引言在一些諸如找出最短路徑和最小生成樹的圖的算法中，用由它52設G=(V,E)是一個有向或無向圖，G的深度優(yōu)先搜索運作如下：1、初始化所有的頂點訪問標志為未訪問；2、任意選擇一個起始頂點，比如說s∈V，并標上已訪問。3、從s的鄰接頂點中選擇任意一個頂點w，訪問該頂點，同時將其標志為被訪問。9.2深度優(yōu)先搜索設G=(V,E)是一個有向或無向圖，G的深度優(yōu)53

3、將訪問指針移至w結(jié)點，將其標志為被訪問，然后從w的臨接結(jié)點中選擇一個未被訪問的結(jié)點，向前繼續(xù)訪問；

4、在訪問過程中，按照上述的深度優(yōu)先的方式向前推進，一旦發(fā)現(xiàn)某一個頂點X的所有鄰接點都被標志為已訪問，訪問指針回退至上一層，繼續(xù)訪問該層沒有被訪問的其他的子節(jié)點。

5、如此往復，直至回退到根節(jié)點為止。3、將訪問指針移至w結(jié)點，將其標志為被訪問，54算法9.1DFSInput:有向或無向圖G=(V,E)。Output:在相應的深度優(yōu)先搜索樹中對頂點的前序和后序。1.predfn0;postdfn02.For每個頂點v∈V3.標記v未訪問//初始化訪問標志4.Endfor5.For每個頂點v∈V6.Ifv未訪問thendfs(v)//調(diào)用訪問7.Endfor算法9.1DFS55過程dfs(v)//遞歸訪問1.標記v已訪問2.predfnpredfn+1

//進來訪問，是前序號3.For每條邊(v,w)∈E4.Ifw標記為未訪問thendfs(w)5.Endfor6.postdfnpostdfn+1

//結(jié)點被訪問完畢，退回時訪問該語句，即后序號算法生成結(jié)構(gòu)：1、樹（全部頂點相連，能夠一次到達）；2、森林（頂點不相連，不能夠一次都到達）。過程dfs(v)//遞歸訪問561、無向圖的情況分析設G=(V,E)是無向圖，作為遍歷的結(jié)果，G的邊分成一下兩種類型。樹邊：深度優(yōu)先搜索樹中的邊，如果在搜索邊(v,w)時，w是首次被訪問，則邊(v,w)是樹邊?；剡叄核衅渌倪叀＠?.1。1、無向圖的情況分析57edcbfahgijedcbfahgij58abcdefghij1,102,93,34,25,16,87,78,69,510,4abcdefghij1,102,93,34,25,16,87592、有向圖的情況

有向圖中的深度優(yōu)先搜索導致結(jié)果：一個或多個(有向)生成樹，樹的多少取決于初始點。（1）選擇某起始點v，深度優(yōu)先搜索一棵樹，它由從v出發(fā)所有可到達的頂點組成。（2）沒有遍歷完所有的頂點，選擇另一個頂點w繼續(xù)（未訪問過頂點），構(gòu)建一顆從w可到達的所有未訪問頂點組成的樹，這個過程繼續(xù)下去直到所有的頂點都被訪問過。（3）重復上述過程，直至所有頂點被訪問完畢。2、有向圖的情況60G的邊分成4種類型：1、樹邊：深度優(yōu)先搜索樹中的邊。如果在搜索邊(v,w)時，w是第一次被訪問，則(v,w)是樹邊。2、回邊：在迄今為止構(gòu)建的深度優(yōu)先搜索樹中，w是v的祖先，并且當搜索(v,w)時頂點w已被標上已訪問，這樣形成的邊(v,w)是回邊。3、前向邊：在迄今為止構(gòu)建的深度優(yōu)先搜索樹中，w是v的后裔，并且當搜索(v,w)時頂點w被標上已訪問，這種形式的邊(v,w)是前向邊。3、橫跨邊：所有其它的邊。見例9.2。G的邊分成4種類型：61cdebafcdebaf62abefcdafebcd1,42,33,14,25,66,51,42,23,14,35,66,5abefcdafebcd1,42,33,14,25,66,563

(1)頂點v被訪問標記為訪問的過程，每一個頂點的調(diào)用耗費是(1)。一共需要n個頂點，所以該過程的總耗費是(n)。（2）算法的步驟1和步驟3分別耗費(1)和(n)時間。//初始化序列號、訪問標志（3）步驟6測試一個頂點是否已標記要耗費(n)。（注意：測試方法是要依次搜索該點的鄰接點，看是否從某個點訪問過它，所以是(n)）

9.2.1深度優(yōu)先搜索的時間復雜性(1)頂點v被訪問標記為訪問的過程，每一個頂點的調(diào)用64（4）測試頂點w是否標記為未訪問，這一步的執(zhí)行次數(shù)等于頂點v的鄰接點數(shù)。

這一步執(zhí)行的總次數(shù)，在有向圖的情況下等于它的邊數(shù)，在無向圖的情況下是邊數(shù)的兩倍。于是，不論是有向圖還是無向圖，這一步的耗費是(m)，（5）算法的總運行時間是：(m+n)。如果圖是連通的或有m≥n,則運行時間簡單地為(m)。但是必須強調(diào)的是，圖假設是用鄰接表表示的。（4）測試頂點w是否標記為未訪問，這一步的執(zhí)行次數(shù)等于659.3深度優(yōu)先搜索的應用

深度優(yōu)先搜索在圖和幾何算法中用得很普遍。在本節(jié)中，我們列舉它的一些重要應用。設G=(V,E)是一個有n個頂點和m條邊的有向或無向圖。為了測試G是否至少有一個回路，我們對G用深度優(yōu)先搜索，如果在搜索過程中探測到一條回邊，那么G是有回路的，否則G是無回路的。

注意G可能不連通，如果G是連通無向圖，那么不需要對圖進行遍歷，因為G是無回路的當且僅當它是一棵樹，則當且僅當m=n-1。9.3.1圖的無回路性9.3深度優(yōu)先搜索的應用設G=(V,E)是一個66給出一個有向無回路圖(dag)G=(V,E)，拓撲排序問題是找出圖頂點的一個線性序列，使得如果(v,w)∈E，那么在這個序中v在w前出現(xiàn)。例如，在圖9.3(a)中所示的有向無回路圖中，頂點的一個可能的拓撲排序是a,b,d,c,e,f,g。我們將假設在這種有向無回路圖中有一個入度是0的唯一的頂點s，如果不是的話，我們可以簡單地添一個新的頂點s，然后讓s到所有入度為0的點加上邊。9.3.2拓撲排序給出一個有向無回路圖(dag)G=(V,E)，拓67abdfcegsabdfcegs68接下來，我們從頂點s起，簡單地對圖G執(zhí)行深度優(yōu)先搜索。當遍歷完成時，計數(shù)器postdfn定義了一個在有向無回路圖中頂點的反撲排序，于是，為了得到這個拓撲序，可以在算法DFS中在計數(shù)器postdfn剛好被增加后，加上一個輸出步，把輸出結(jié)果翻轉(zhuǎn)過來就是我們需要的拓撲序。接下來，我們從頂點s起，簡單地對圖G執(zhí)行深度優(yōu)先69

關(guān)節(jié)點:

在多于兩個頂點的無向圖G中，存在一個頂點v，如果有不同于v的兩個頂點u和w，在u和w間的任何路徑都必定經(jīng)過頂點v。這樣，如果G是連通的，移去v和與它關(guān)聯(lián)的邊，將產(chǎn)生G的非連通子圖（森林）。一個圖如果是連通的并且沒有關(guān)節(jié)點則稱為是雙連通的。9.3.3尋找圖的關(guān)節(jié)點關(guān)節(jié)點:9.3.3尋找圖的關(guān)節(jié)點70由深度優(yōu)先生成樹的特性可以得到如下結(jié)論：1、根是一個關(guān)節(jié)點當且僅當在深度優(yōu)先搜索樹中，它有兩個或更多的兒子；原因：圖中不存在連接不同子樹頂點的邊，刪掉根結(jié)點后，生成樹就變成了森林。2、根以外的其他結(jié)點V，如果其某棵子樹的根和子樹中的其他結(jié)點均沒有指向該結(jié)點v的祖先的回邊?；蛘撸焊酝獾捻旤cv是一個關(guān)節(jié)點當且僅當v有一個兒子w，使得β(w)≥α(v)。由深度優(yōu)先生成樹的特性可以得到如下結(jié)論：71為了找出關(guān)節(jié)點的集合，在圖G上執(zhí)行一個深度優(yōu)先搜索遍歷。在遍歷的過程中，對每個頂點v保持兩個標號：α(v)和β(v)，α(v)只是深度優(yōu)先搜索算法中的predfn，每次調(diào)用深度優(yōu)先搜索過程，就加1，β(v)初始化為α(v)，但在后來的遍歷過程中可以改變。對于每一個訪問的頂點，令β(v)是下面幾個中的最小值。

α(v)；//葉子結(jié)點α(u)，對于每個頂點u,(v,u)是回邊；β(w)，在深度優(yōu)先搜索樹中的每條邊(v,w)。為了找出關(guān)節(jié)點的集合，在圖G上執(zhí)行一個深度72上述β(v)值的變化是：一旦某個點出現(xiàn)回邊，則該結(jié)點的β(v)值必然變小為其祖先結(jié)點k的β()值。如果某個結(jié)點的β值大于其α值，則肯定有一個子結(jié)點，必然是關(guān)節(jié)點；如果該值小于其α值，肯定是有回邊了。如果等于α值，則肯定是沒有孩子了。

使用這個值的目的就是在回訪結(jié)點的過程中，通過判斷結(jié)點的α與β值的關(guān)系以得到該結(jié)點是什么結(jié)點

上述β(v)值的變化是：一旦某個點出現(xiàn)回邊，則73算法9.2ARTICPOINTSINPUT:連通無向圖G=(V,E)。OUTPUT:包含G的所有可能關(guān)節(jié)點的數(shù)組A[1…n]。1.設s為起始頂點2.for每個頂點v∈V3.標記v未訪問4.endfor//初始化全部結(jié)點為沒有訪問5.predfn0;count0;rootdegree06.dfs(s)//從初始結(jié)點開始訪問算法9.2ARTICPOINTS74過程dfs(v)1.標記v已訪問；artpointfalse;//關(guān)節(jié)點標記predfnpredfn+1//標記序號2.α(v)predfn;

β(v)predfn//初始化訪問序號3.For每條邊(v,w)∈E4.If(v,w)為樹邊then5.dfs(w)//深入開始訪問后續(xù)結(jié)點6.Ifv=sthen

//樹根結(jié)點7.rootdegreerootdegree+18.Ifrootdegree=2thenartpointtrue//根節(jié)點至少存在兩個子樹，是關(guān)節(jié)結(jié)點9.Else

過程dfs(v)75

10.β(v)min{β(v),β(w)}11.Ifβ(w)≥α(v)thenartpointtrue//有孩子就標記為關(guān)節(jié)結(jié)點12.Endif13.Elseif(v,w)是回邊then//v!=s

β(v)min{β(v),α(w)}14.Elsedonothing{w是v的父親}15.Endif16.Endfor17.Ifartpointthen18.countcount+119.A[count]

v20.Endif10.β(v)min{β(76（1）首先，算法執(zhí)行必要的初始化，特別地，count是關(guān)節(jié)點的個數(shù)，rootdegree是深度優(yōu)先搜索樹根的度，這在后來決定根是否是關(guān)節(jié)點時是需要的。（2）接著深度優(yōu)先搜索從根開始著手，對于每一個訪問的頂點v，α(v)和β(v)用predfn來初始化。（3）在搜索從某頂點w退回到v時，要做兩件事，首先，如果發(fā)現(xiàn)β(w)比β(v)小，β(v)被設置為β(w)，其次，如果β(w)≥α(v)，那么這就指出v是一個關(guān)節(jié)點，因為從w到v的祖先頂點必須經(jīng)過v。（1）首先，算法執(zhí)行必要的初始化，特別地，77這說明在圖9.4種，可以看到，從以w為根的子樹到u的任何路徑必定包括v，因此v是一個關(guān)節(jié)點。以w為根的子樹包含一個或多個連通分支。在這個圖中，根u是關(guān)節(jié)點，因為它的度大于1。見例9.3。這說明在圖9.4種，可以看到，從以w為根的子樹到u的78edcbfahgijedcbfahgij79abcdefghij1,12,13,34,35,36,17,18,89,810,8abcdefghij1,12,13,34,35,36,17,80（1）初始化各個頂點；（2）從a-e開始搜索，一直到e均是正常搜索，各個數(shù)值依次遞增增長；（3）搜索到e時，找到一個回邊(e,c)，則e的β(e)=min{a[c]=3；a[e]=5,β[c]=3}=3；（4）回退至d點時，該點的β[d]=3;(原來是4);(5)回退到c點，β[c]=3，由于β[d]>=a[c]，所以該結(jié)點是關(guān)節(jié)點。(6)回退到b結(jié)點，β[c]>=a[b]，所以b也是一個關(guān)節(jié)點。此時，發(fā)現(xiàn)b結(jié)點還有一個分支，繼續(xù)搜索該分支。（1）初始化各個頂點；81（1）探測到（j,h）是一個回邊，所以將

β[j]=a[h]=8；（2）回到i點，該點的β[i]也被改為8；（3）同理，對于h點來講，其β[h]也被置為8；此時，由于β[i]>a[h],所以h是關(guān)節(jié)點；（4）回退到g點,同樣存在β[h]>a[g]，所以該點也是關(guān)節(jié)點；檢測到該點存在回路，所以將其β[g]值置為其祖先結(jié)點的值=1；（5）β[f]β[b]也被置為1,搜索回到a結(jié)點，因為a結(jié)點只有一個分支孩子，所以a不是關(guān)節(jié)點

（1）探測到（j,h）是一個回邊，所以將82edcbfahgijedcbfahgij83abcdefghij1,12,13,34,35,36,17,18,79,710,7abcdefghij1,12,13,34,35,36,17,84給出一個有向圖G=(V,E)，G中的強連通分支是它頂點的極大集，在該集中，每一對頂點間都存在一條路徑。下面的算STRONGCONNECTCOMP用深度優(yōu)先搜索來確定在有向圖中的所有的強連通分支。9.3.4強連通分支給出一個有向圖G=(V,E)，G中的強連通分支是85算法9.3STRONGCONNECTCOMPINPUT:有向圖G=(V,E)OUTPUT:G中的強連通分支1.在圖G上執(zhí)行深度優(yōu)先搜索，對每一個頂點賦給相應的postdfn值。2.顛倒圖G中邊的方向，構(gòu)成一個新的圖3.從具有最大postdfn數(shù)值的頂點開始，在上執(zhí)行深度優(yōu)先搜索，如果深度優(yōu)先搜索不能到達所有的頂點，則在余下的頂點中找出一個postdfn數(shù)值最大的頂點，開始下一