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

1

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

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

11

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

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

算法BFS同時可生成一棵廣度優(yōu)先樹（森林）。初始時，樹中只包含搜索的源結點作為根結點。在搜索中，對于E結點u，每發(fā)現(xiàn)一個白色結點v，便將結點v和邊<u,v>添加到樹中。在廣度優(yōu)先樹中，稱結點u是結點v的雙親結點。如果結點v是從根結點到結點w的路徑上的一個結點，則稱v是w的祖先，w是v的后裔。由于從一個給定的起始結點u出發(fā)的廣度優(yōu)先搜索，只能訪問從u出發(fā)有路徑可達的那些結點。如果要遍歷整個有向圖，還需從圖中另選未訪問的結點作為起始結點，再次進行廣度優(yōu)先搜索。15圖4-2給出了以結點0為起點，廣度優(yōu)先遍歷圖4-1(a)的有向圖G所得到的廣度優(yōu)先森林，它包含兩棵廣度優(yōu)先樹。返回01236540123654圖G的廣度優(yō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結點x的某個后繼結點y后，立即使y成為新的E結點，去訪問y的后繼結點，直到完全檢測結點y后，x才能再次成為E結點，繼續(xù)訪問x的其他未訪問的后繼結點。深度優(yōu)先搜索使用堆棧為活結點表。1.深度優(yōu)先遍歷算法

19

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

算法同時可生成一棵深度優(yōu)先樹。初始時，樹中只包含搜索的源結點作為根結點。在搜索中，一個結點，每發(fā)現(xiàn)一個白色結點，便將結點及邊添加到樹中。對比01236540123654圖G的深度優(yōu)先森林254.深度優(yōu)先搜索的性質定理4-2括號定理在對有向圖或無向圖G=(V,E)的任何深度優(yōu)先搜索中，對于圖中任意兩結點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)：其余的邊。當一條邊既是反向邊又是正向邊時，則認為它是反向邊。課堂練習對于下圖及其鄰接表，寫出以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é)點：在一個無向連通圖G=(V,E)中，可能存在某個（或多個）結點a，使得一旦刪除a及其相關聯(lián)的邊，圖G不再是連通圖，則結點a稱為圖G的關節(jié)點。橋：如果刪除圖G的某條邊b,該圖分離成兩個非空子圖，則稱邊b是圖G的橋。30

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

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

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

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

性質4-3

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

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

從結點u出發(fā)，有兩種途徑可以達到樹中其他結點：一、自結點u經過一條反向邊到達某個結點x；二、自結點u出發(fā)，經過u的某個孩子w，以及一條由w出發(fā)的由樹邊組成的一條路徑和反向邊到達某個結點y；Low[u]是結點u通過一條子孫路徑和至多隨后一條反向邊所能到達的結點的最低深度優(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不是根，當且僅當結點u有一個孩子w，其Low[w]≥d[u]時，u是一個關節(jié)點41

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

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