第4章基本搜索和遍歷方法

1

第4章基本搜索和遍歷方法4.1基本概念4.2圖的搜索和遍歷4.3雙連通分量4.4與或圖×4.1基本概念2搜索和遍歷是計算機問題求解最常用的技術(shù)之一。搜索（search）是一種通過系統(tǒng)地檢查給定數(shù)據(jù)對象的每個結(jié)點，尋找一條從開始結(jié)點到答案結(jié)點的路徑，最終輸出問題解的求解方法。遍歷(traversal)要求系統(tǒng)地檢查數(shù)據(jù)對象的每個結(jié)點。根據(jù)被遍歷的數(shù)據(jù)對象的結(jié)構(gòu)不同，可分成樹遍歷和圖遍歷。4.1基本概念狀態(tài)空間用于描述所求問題的各種可能的情況，每一種情況對應(yīng)于狀態(tài)空間中的一個狀態(tài)。初始狀態(tài)：代表搜索開始。目標狀態(tài)（答案狀態(tài)）：一個或多個狀態(tài)代表已經(jīng)求得問題解的情況。問題的狀態(tài)空間常用一棵樹或一個圖表示。樹（圖）中的一個結(jié)點代表問題的一個狀態(tài)，問題的狀態(tài)空間中的所有狀態(tài)形成一棵狀態(tài)空間樹（圖）。問題的求解過程:從起始狀態(tài)出發(fā)，以某種次序系統(tǒng)地檢查狀態(tài)空間中的每一個狀態(tài)，搜索代表問題解的答案狀態(tài)的過程。3一般來說，使用搜索技術(shù)來求解計算機問題，需要使用狀態(tài)空間的概念精確地描述問題。無知搜索（盲目搜索或窮舉搜索），是最簡單的搜索狀態(tài)空間樹的方法。按照事先約定的某種次序，系統(tǒng)地在狀態(tài)空間中搜索目標狀態(tài)，而無須對狀態(tài)空間有較多了解。4有知搜索：運用問題的相關(guān)知識，克服無知搜索的盲目性，有效地指導(dǎo)搜索過程，使之盡快到達答案狀態(tài)。啟發(fā)式搜索：采用經(jīng)驗法則的搜索方法。啟發(fā)式方法一邊搜索，一邊評估達到目標狀態(tài)的剩余距離，這種評估依賴于已有的關(guān)于問題領(lǐng)域的知識和經(jīng)驗規(guī)則。4.2圖的搜索和遍歷4.2.1搜索方法在樹形結(jié)構(gòu)中，一個結(jié)點的直接后繼結(jié)點是它的孩子結(jié)點。在圖形結(jié)構(gòu)中，一個結(jié)點的后繼結(jié)點是鄰接于該結(jié)點的所有鄰接點。5遍歷：遵循某種次序，系統(tǒng)地訪問一個數(shù)據(jù)結(jié)構(gòu)的全部元素。實現(xiàn)遍歷運算的關(guān)鍵是規(guī)定結(jié)點被訪問的次序。6為深入認識搜索算法的特點，將被搜索的結(jié)點按其狀態(tài)分成4類：未訪問、未檢測、已檢測和正擴展。未訪問狀態(tài)：一個結(jié)點x尚未訪問；未檢測狀態(tài)：結(jié)點x自身已訪問，但x的后繼結(jié)點尚未全部訪問；已檢測狀態(tài)：當(dāng)算法訪問了x的所有后繼結(jié)點時，就稱x已由此算法檢測；正擴展?fàn)顟B(tài)：算法正從結(jié)點x出發(fā)，訪問x的某個后繼結(jié)點,x被稱為擴展結(jié)點，簡稱E-結(jié)點。在算法執(zhí)行的任何時刻，最多只有一個結(jié)點為E-結(jié)點，但可以有多個結(jié)點處于未檢測狀態(tài)。由于一個搜索算法總是從一個未檢測結(jié)點出發(fā)，獲取下一個被訪問的結(jié)點，因此，保存所有未檢測結(jié)點對于搜索算法是十分重要的?；罱Y(jié)點：指未檢測結(jié)點。死結(jié)點：指已檢測結(jié)點。在搜索算法的執(zhí)行中，需要有一個數(shù)據(jù)結(jié)構(gòu)保存這些活結(jié)點，被稱為活結(jié)點表。7依據(jù)如何選擇E-結(jié)點的規(guī)則不同，得到兩種不同的搜索算法：深度優(yōu)先搜索和廣度優(yōu)先搜索。8

4.2.2鄰接表類設(shè)有向圖G=(V,E)有n個結(jié)點。圖4-1(b)給出了圖4-1(a)的鄰接表存儲結(jié)構(gòu)。4.2.3廣度優(yōu)先搜索9廣度優(yōu)先搜索：一個結(jié)點x一旦成為E結(jié)點，算法將依次訪問完它的全部未訪問的后繼結(jié)點。每訪問一個結(jié)點，就將它加入活結(jié)點表。直到x檢測完畢，算法才從活結(jié)點表另選一個活結(jié)點作為E結(jié)點。廣度優(yōu)先搜索以隊列作為活結(jié)點表，因而也被稱為FIFO搜索。10為了實現(xiàn)搜索，也為了形象地刻畫圖搜索算法的執(zhí)行過程，算法中使用白色、灰色和黑色分別代表結(jié)點處于未訪問、未檢測和已檢測三種不同狀態(tài)。E結(jié)點是灰色結(jié)點，任何時刻至多有一個灰色結(jié)點處于擴展?fàn)顟B(tài)。使用結(jié)點的顏色替代標志位標記一個結(jié)點是否已訪問。為了保持搜索的軌跡，廣度優(yōu)先搜索為每個頂點著色：白色、灰色或黑色。算法開始前所有頂點都是白色，隨著搜索的進行，各頂點會逐漸變成灰色，然后成為黑色。1.廣度優(yōu)先遍歷算法

11

假設(shè)初始時圖G的所有結(jié)點都為白色結(jié)點，那么從圖中某個結(jié)點u出發(fā)的廣度優(yōu)先搜索圖的過程可以描述為：訪問結(jié)點u，結(jié)點u著灰色；然后依次訪問u的各個白色鄰接點，將它們著灰色；訪問完結(jié)點u的所有白色鄰接點，結(jié)點u著黑色；接著再依次訪問分別與這些鄰接點相鄰接的白色結(jié)點……隊列Q保存搜索過程中產(chǎn)生的活結(jié)點。12

舉例：廣度優(yōu)先搜索在一個無向圖（結(jié)點S開始）上的執(zhí)行過程132.廣度優(yōu)先樹14

算法BFS同時可生成一棵廣度優(yōu)先樹（森林）。初始時，樹中只包含搜索的源結(jié)點作為根結(jié)點。在搜索中，對于E結(jié)點u，每發(fā)現(xiàn)一個白色結(jié)點v，便將結(jié)點v和邊<u,v>添加到樹中。在廣度優(yōu)先樹中，稱結(jié)點u是結(jié)點v的雙親結(jié)點。如果結(jié)點v是從根結(jié)點到結(jié)點w的路徑上的一個結(jié)點，則稱v是w的祖先，w是v的后裔。由于從一個給定的起始結(jié)點u出發(fā)的廣度優(yōu)先搜索，只能訪問從u出發(fā)有路徑可達的那些結(jié)點。如果要遍歷整個有向圖，還需從圖中另選未訪問的結(jié)點作為起始結(jié)點，再次進行廣度優(yōu)先搜索。15圖4-2給出了以結(jié)點0為起點，廣度優(yōu)先遍歷圖4-1(a)的有向圖G所得到的廣度優(yōu)先森林，它包含兩棵廣度優(yōu)先樹。返回01236540123654圖G的廣度優(yōu)先森林課堂練習(xí)對于下面一個圖及其存儲結(jié)構(gòu)，寫出以v2、v8為起始點的廣度優(yōu)先遍歷序列，并畫出廣度優(yōu)先樹。16v1v2v3v4v5v6v7v801v12v23v34v45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v517參考答案：以v2為起始點：v2-v1-v4-v5-v3-v8-v6-v7以v8為起始點：v8-v4-v5-v2-v1-v3-v6-v7v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v84.2.4深度優(yōu)先搜索18

深度優(yōu)先搜索：訪問E結(jié)點x的某個后繼結(jié)點y后，立即使y成為新的E結(jié)點，去訪問y的后繼結(jié)點，直到完全檢測結(jié)點y后，x才能再次成為E結(jié)點，繼續(xù)訪問x的其他未訪問的后繼結(jié)點。深度優(yōu)先搜索使用堆棧為活結(jié)點表。1.深度優(yōu)先遍歷算法

19

初始時，圖G的所有結(jié)點都為白色結(jié)點，從圖中某個結(jié)點u出發(fā)的深度優(yōu)先搜索過程DFS可以描述為：（1）訪問結(jié)點u,對結(jié)點u著灰色；（2）依次從u的白色鄰接點出發(fā)，深度優(yōu)先搜索圖G。為了訪問有向圖中的所有結(jié)點，必須從圖中另選白色結(jié)點為起始結(jié)點，再次進行深度優(yōu)先搜索。可能需要重復(fù)多次，直到圖中結(jié)點均已訪問。20為便于分析深度優(yōu)先搜索算法的執(zhí)行情況，在搜索中為每個結(jié)點添加時間戳。深度優(yōu)先搜索對每個結(jié)點u加蓋兩個時間戳d[u]和f[u]：第1個時間：當(dāng)結(jié)點u著灰色時，由d[u]記錄；第2個時間：當(dāng)結(jié)點u著黑色時，由f[u]記錄。在時刻d[u]之前結(jié)點u為白色，在時刻d[u]和f[u]之間為灰色，f[u]以后變?yōu)楹谏?。初始時，對所有結(jié)點u，d[u]=f[u]=0，時鐘的初值為0.21圖2說明了深度優(yōu)先搜索在有向圖（u出發(fā)）上的執(zhí)行過程。2223加粗的實線邊--樹枝虛線邊--非樹枝的邊，分別標明B、C、F以表示反向邊、交叉邊、正向邊。2.深度優(yōu)先樹24

算法同時可生成一棵深度優(yōu)先樹。初始時，樹中只包含搜索的源結(jié)點作為根結(jié)點。在搜索中，一個結(jié)點，每發(fā)現(xiàn)一個白色結(jié)點，便將結(jié)點及邊添加到樹中。對比01236540123654圖G的深度優(yōu)先森林254.深度優(yōu)先搜索的性質(zhì)定理4-2括號定理在對有向圖或無向圖G=(V,E)的任何深度優(yōu)先搜索中，對于圖中任意兩結(jié)點u和v，下述三個條件中有且僅有一條成立：(1)區(qū)間[d[u],f[u]]和區(qū)間[d[v],f[v]]是完全分離的，且在深度優(yōu)先森林中，u和v互不為后裔；(2)區(qū)間[d[u],f[u]]完全包含區(qū)間[d[v],f[v]]，且在深度優(yōu)先樹中v是u的后裔；(3)區(qū)間[d[v],f[v]]完全包含區(qū)間[d[u],f[u]]，且在深度優(yōu)先樹中u是v的后裔；5.邊的分類26

（1）樹邊(treeedge)：深度優(yōu)先森林的邊。（2）反向邊B(backedge)：深度優(yōu)先樹中從后裔到祖先的邊，環(huán)也被認為是反向邊。（3）正向邊F(forwardedge)：深度優(yōu)先樹中從祖先到后裔的非樹邊。（4）交叉邊C(crossedge)：其余的邊。當(dāng)一條邊既是反向邊又是正向邊時，則認為它是反向邊。課堂練習(xí)對于下圖及其鄰接表，寫出以v2、v8為起始點的深度優(yōu)先遍歷序列，并畫出深度優(yōu)先樹，標出邊的分類。2701v12v23v34v45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8參考答案：以v2為起始點：v2-v1-v3-v6-v7-v4-v8-v5以v8為起始點：v8-v4-v2-v1-v3-v6-v7-v528v1v2v3v4v5v6v7v8BBv1v2v3v4v5v6v7v8BB294.3雙連通分量4.3.1基本概念

雙連通圖：一個無向圖的任意兩個結(jié)點之間至少有兩條不同的路徑相通。針對無向圖關(guān)節(jié)點：在一個無向連通圖G=(V,E)中，可能存在某個（或多個）結(jié)點a，使得一旦刪除a及其相關(guān)聯(lián)的邊，圖G不再是連通圖，則結(jié)點a稱為圖G的關(guān)節(jié)點。橋：如果刪除圖G的某條邊b,該圖分離成兩個非空子圖，則稱邊b是圖G的橋。30

圖4-5(a)中的圖G有哪些關(guān)節(jié)點？哪條邊是橋？(a)無向連通圖G01326547(b)刪除圖G的關(guān)節(jié)點1(c)刪除圖G的橋<6,1>03265470132654731

雙連通分量：無向連通圖G的極大雙連通子圖。一個無向圖可以分成多個雙連通分量，它們將圖中的邊劃分為若干個子集（不是將結(jié)點劃分子集）。雙連通圖：無向連通圖G中不包含任何關(guān)節(jié)點。0132654732

從圖中可以看出：1.兩個雙連通分量至多有一個公共結(jié)點，且此結(jié)點必為關(guān)節(jié)點。2.兩個雙連通分量不可能共有同一條邊。3.每個雙連通分量至少包含兩個結(jié)點（除非無向圖只有一個結(jié)點）(a)無向連通圖G01326547雙連通分量1246571603233對于一個無向連通圖G，下列說法是等價的：（1）圖G是雙連通的；（2）圖G的任意兩個結(jié)點之間存在簡單回路；（3）圖G中不包含關(guān)節(jié)點。簡單回路：在一個回路中，出現(xiàn)的邊互不相同。4.3.2發(fā)現(xiàn)關(guān)節(jié)點在網(wǎng)絡(luò)應(yīng)用中，通常不希望網(wǎng)絡(luò)中存在關(guān)節(jié)點。因為這意味著一旦在這些位置出現(xiàn)故障，勢必導(dǎo)致大面積的通信中斷。因此判定一個無向圖是否雙連通圖，在圖中發(fā)現(xiàn)關(guān)節(jié)點及求圖的雙連通分量是很有實際意義的問題。34一個無向連通圖不是雙連通圖的充要條件是圖中存在關(guān)節(jié)點。在無向圖中識別關(guān)節(jié)點的最簡單做法是：從圖G中刪除一個結(jié)點a和該結(jié)點的關(guān)聯(lián)邊，再檢查圖G的連通性。如果圖G因此而不再是連通圖，則結(jié)點a是關(guān)節(jié)點。35需借助圖的深度優(yōu)先生成樹來識別關(guān)節(jié)點。

假設(shè)從某個頂點V0出發(fā)對連通圖進行深度優(yōu)先搜索，則可得到一棵深度優(yōu)先生成樹，樹上包含圖的所有頂點。36ahgcbfde1abcdefgh2345678例如:下列連通圖中的關(guān)節(jié)點？結(jié)點a,c是關(guān)節(jié)點深度優(yōu)先生成樹(a為根結(jié)點)結(jié)點的深度優(yōu)先數(shù)，記錄了結(jié)點被訪問的先后次序37

性質(zhì)4-3

給定無向連通圖G=(V,E),S=(V,T)是圖G的一棵深度優(yōu)先樹，圖中結(jié)點a是一個關(guān)節(jié)點，當(dāng)且僅當(dāng)（1）a是根，且a至少有兩個孩子。（2）或者a不是根，且a的某棵子樹上沒有指向a的祖先的反向邊。求圖G關(guān)節(jié)點的算法38

深度優(yōu)先數(shù)：在深度優(yōu)先搜索中對每個結(jié)點u加蓋兩個時間戳。其中，d[u]記錄結(jié)點u被訪問的時間，也稱為結(jié)點的深度優(yōu)先數(shù)；為了實現(xiàn)這一算法，需要對圖中每個結(jié)點定義一個與優(yōu)先數(shù)有關(guān)的量Low。最低深度優(yōu)先數(shù)：Low[u]表示從結(jié)點u出發(fā)，經(jīng)過某條路徑可以達到深度優(yōu)先樹其他結(jié)點的最小優(yōu)先數(shù)；39

從結(jié)點u出發(fā)，有兩種途徑可以達到樹中其他結(jié)點：一、自結(jié)點u經(jīng)過一條反向邊到達某個結(jié)點x；二、自結(jié)點u出發(fā)，經(jīng)過u的某個孩子w，以及一條由w出發(fā)的由樹邊組成的一條路徑和反向邊到達某個結(jié)點y；Low[u]是結(jié)點u通過一條子孫路徑和至多隨后一條反向邊所能到達的結(jié)點的最低深度優(yōu)先數(shù)。40

定義4-1：Low[u]定義如下：Low[u]=min{d[u],

min{Low[w]|w是u的孩子}，min{d[x]|(u,x)是一條反向邊}}圖4-9深度優(yōu)先搜索和深度優(yōu)先數(shù)0132654707123456如果u不是根，當(dāng)且僅當(dāng)結(jié)點u有一個孩子w，其Low[w]≥d[u]時，u是一個關(guān)節(jié)點41

圖中每個結(jié)點邊上的偶對(d,Low)代表該結(jié)點的相應(yīng)值。例如，結(jié)點2邊上的(1,0)代表d[2]=1，Low[2]=0.圖4-10結(jié)點的d和Low值01326547(0,0)(6,4)(5,4)(4,4)(3,1)(2,1)(1,0)(7,0)4.3.3構(gòu)造雙連通圖42

發(fā)現(xiàn)關(guān)節(jié)點和求雙連通分量的