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

1

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

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

11

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

舉例：廣度優(yōu)先搜索在一個(gè)無(wú)向圖（結(jié)點(diǎn)S開(kāi)始）上的執(zhí)行過(guò)程132.廣度優(yōu)先樹(shù)14

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

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

19

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

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

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

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

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

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

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

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

性質(zhì)4-3

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

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

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

圖中每個(gè)結(jié)點(diǎn)邊上的偶對(duì)(d,Low)代表該結(jié)點(diǎn)的相應(yīng)值。例如，結(jié)點(diǎn)2邊上的(1,0)代表d[2]=1，Low[2]=0.圖4-10結(jié)點(diǎn)的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é)點(diǎn)和求雙連通分量的