1 引言

遍歷是指從某個(gè)節(jié)點(diǎn)出發(fā)，按照一定的的搜索路線，依次訪問對數(shù)據(jù)結(jié)構(gòu)中的全部節(jié)點(diǎn)，且每個(gè)節(jié)點(diǎn)僅訪問一次。

在二叉樹基礎(chǔ)中，介紹了對于樹的遍歷。樹的遍歷是指從根節(jié)點(diǎn)出發(fā)，按照一定的訪問規(guī)則，依次訪問樹的每個(gè)節(jié)點(diǎn)信息。樹的遍歷過程，根據(jù)訪問規(guī)則的不同主要分為四種遍歷方式：

（1）先序遍歷（2）中序遍歷（3）后序遍歷（4）層次遍歷

類似的，圖的遍歷是指，從給定圖中任意指定的頂點(diǎn)（稱為初始點(diǎn)）出發(fā)，按照某種搜索方法沿著圖的邊訪問圖中的所有頂點(diǎn)，使每個(gè)頂點(diǎn)僅被訪問一次，這個(gè)過程稱為圖的遍歷。遍歷過程中得到的頂點(diǎn)序列稱為圖遍歷序列。

圖的遍歷過程中，根據(jù)搜索方法的不同，又可以劃分為兩種搜索策略：

（1）深度優(yōu)先搜索（DFS，Depth First Search）（2）廣度優(yōu)先搜索（BFS，Breadth First Search）

2 深度優(yōu)先搜索

2.1 算法思想

深度優(yōu)先搜索思想：假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)均未被訪問，則從某個(gè)頂點(diǎn)v出發(fā)，首先訪問該頂點(diǎn)，然后依次從它的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。若此時(shí)尚有其他頂點(diǎn)未被訪問到，則另選一個(gè)未被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。

2.2 算法特點(diǎn)

深度優(yōu)先搜索是一個(gè)遞歸的過程。首先，選定一個(gè)出發(fā)點(diǎn)后進(jìn)行遍歷，如果有鄰接的未被訪問過的節(jié)點(diǎn)則繼續(xù)前進(jìn)。若不能繼續(xù)前進(jìn)，則回退一步再前進(jìn)，若回退一步仍然不能前進(jìn)，則連續(xù)回退至可以前進(jìn)的位置為止。重復(fù)此過程，直到所有與選定點(diǎn)相通的所有頂點(diǎn)都被遍歷。

深度優(yōu)先搜索是遞歸過程，帶有回退操作，因此需要使用棧存儲(chǔ)訪問的路徑信息。當(dāng)訪問到的當(dāng)前頂點(diǎn)沒有可以前進(jìn)的鄰接頂點(diǎn)時(shí)，需要進(jìn)行出棧操作，將當(dāng)前位置回退至出棧元素位置。

2.3 圖解過程

2.3.1 無向圖深度優(yōu)先搜索

以圖2.3.1.1中所示無向圖說明深度優(yōu)先搜索遍歷過程。

圖2.3.1.1

（1）首先選取頂點(diǎn)A為起始點(diǎn)，輸出A頂點(diǎn)信息，且將A入棧，并標(biāo)記A為已訪問頂點(diǎn)。

（2）A的鄰接頂點(diǎn)有C、D、F，從中任意選取一個(gè)頂點(diǎn)前進(jìn)。這里我們選取C頂點(diǎn)為前進(jìn)位置頂點(diǎn)。輸出C頂點(diǎn)信息，將C入棧，并標(biāo)記C為已訪問頂點(diǎn)。當(dāng)前位置指向頂點(diǎn)C。

（3）頂點(diǎn)C的鄰接頂點(diǎn)有A、D和B，此時(shí)A已經(jīng)標(biāo)記為已訪問頂點(diǎn)，因此不能繼續(xù)訪問。從B或者D中選取一個(gè)頂點(diǎn)前進(jìn)，這里我們選取B頂點(diǎn)為前進(jìn)位置頂點(diǎn)。輸出B頂點(diǎn)信息，將B入棧，標(biāo)記B頂點(diǎn)為已訪問頂點(diǎn)。當(dāng)前位置指向頂點(diǎn)B。

（4）頂點(diǎn)B的鄰接頂點(diǎn)只有C、E，C已被標(biāo)記，不能繼續(xù)訪問，因此選取E為前進(jìn)位置頂點(diǎn)，輸出E頂點(diǎn)信息，將E入棧，標(biāo)記E頂點(diǎn)，當(dāng)前位置指向E。

（5）頂點(diǎn)E的鄰接頂點(diǎn)均已被標(biāo)記，此時(shí)無法繼續(xù)前進(jìn)，則需要進(jìn)行回退。將當(dāng)前位置回退至頂點(diǎn)B，回退的同時(shí)將E出棧。

（6）頂點(diǎn)B的鄰接頂點(diǎn)也均被標(biāo)記，需要繼續(xù)回退，當(dāng)前位置回退至C，回退同時(shí)將B出棧。

（7）頂點(diǎn)C可以前進(jìn)的頂點(diǎn)位置為D，則輸出D頂點(diǎn)信息，將D入棧，并標(biāo)記D頂點(diǎn)。當(dāng)前位置指向頂點(diǎn)D。

（8）頂點(diǎn)D沒有前進(jìn)的頂點(diǎn)位置，因此需要回退操作。將當(dāng)前位置回退至頂點(diǎn)C，回退同時(shí)將D出棧。

（9）頂點(diǎn)C沒有前進(jìn)的頂點(diǎn)位置，繼續(xù)回退，將當(dāng)前位置回退至頂點(diǎn)A，回退同時(shí)將C出棧。

（10）頂點(diǎn)A前進(jìn)的頂點(diǎn)位置為F，輸出F頂點(diǎn)信息，將F入棧，并標(biāo)記F。將當(dāng)前位置指向頂點(diǎn)F。

（11）頂點(diǎn)F的前進(jìn)頂點(diǎn)位置為G，輸出G頂點(diǎn)信息，將G入棧，并標(biāo)記G。將當(dāng)前位置指向頂點(diǎn)G。

（12）頂點(diǎn)G沒有前進(jìn)頂點(diǎn)位置，回退至F。當(dāng)前位置指向F，回退同時(shí)將G出棧。

（13）頂點(diǎn)F沒有前進(jìn)頂點(diǎn)位置，回退至A，當(dāng)前位置指向A，回退同時(shí)將F出棧。

（14）頂點(diǎn)A沒有前進(jìn)頂點(diǎn)位置，繼續(xù)回退，棧為空，則以A為起始的遍歷結(jié)束。若圖中仍有未被訪問的頂點(diǎn)，則選取未訪問的頂點(diǎn)為起始點(diǎn)，繼續(xù)執(zhí)行此過程。直至所有頂點(diǎn)均被訪問。

（15）采用深度優(yōu)先搜索遍歷順序?yàn)锳->C->B->E->D->F->G。

2.3.2 有向圖深度優(yōu)先搜索

以圖2.3.2.1中所示有向圖說明深度優(yōu)先搜索遍歷過程。

圖2.3.2.1 有向圖

（1）以頂點(diǎn)A為起始點(diǎn)，輸出A，將A入棧，并標(biāo)記A。當(dāng)前位置指向A。

（2）以A為尾的邊只有1條，且邊的頭為頂點(diǎn)B，則前進(jìn)位置為頂點(diǎn)B，輸出B，將B入棧，標(biāo)記B。當(dāng)前位置指向B。

（3）頂點(diǎn)B可以前進(jìn)的位置有C與F，選取F為前進(jìn)位置，輸出F，將F入棧，并標(biāo)記F。當(dāng)前位置指向F。

（4）頂點(diǎn)F的前進(jìn)位置為G，輸出G，將G入棧，并標(biāo)記G。當(dāng)前位置指向G。

（5）頂點(diǎn)G沒有可以前進(jìn)的位置，則回退至F，將F出棧。當(dāng)前位置指向F。

（6）頂點(diǎn)F沒有可以前進(jìn)的位置，繼續(xù)回退至B，將F出棧。當(dāng)前位置指向B。

（7）頂點(diǎn)B可以前進(jìn)位置為C和E，選取E，輸出E，將E入棧，并標(biāo)記E。當(dāng)前位置指向E。

（8）頂點(diǎn)E的前進(jìn)位置為D，輸出D，將D入棧，并標(biāo)記D。當(dāng)前位置指向D。

（9）頂點(diǎn)D的前進(jìn)位置為C，輸出C，將C入棧，并標(biāo)記C。當(dāng)前位置指向C。

（10）頂點(diǎn)C沒有前進(jìn)位置，進(jìn)行回退至D，回退同時(shí)將C出棧。

（11）繼續(xù)執(zhí)行此過程，直至棧為空，以A為起始點(diǎn)的遍歷過程結(jié)束。若圖中仍有未被訪問的頂點(diǎn)，則選取未訪問的頂點(diǎn)為起始點(diǎn)，繼續(xù)執(zhí)行此過程。直至所有頂點(diǎn)均被訪問。

2.4 算法分析

當(dāng)圖采用鄰接矩陣存儲(chǔ)時(shí)，由于矩陣元素個(gè)數(shù)為n^2，因此時(shí)間復(fù)雜度就是O(n^2)。

當(dāng)圖采用鄰接表存儲(chǔ)時(shí)，鄰接表中只是存儲(chǔ)了邊結(jié)點(diǎn)(e條邊，無向圖也只是2e個(gè)結(jié)點(diǎn))，加上表頭結(jié)點(diǎn)為n（也就是頂點(diǎn)個(gè)數(shù)），因此時(shí)間復(fù)雜度為O(n+e)。

3 廣度優(yōu)先搜索

3.1 算法思想

廣度優(yōu)先搜索思想：從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問v的各個(gè)未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使得“先被訪問的頂點(diǎn)的鄰接點(diǎn)先于后被訪問的頂點(diǎn)的鄰接點(diǎn)被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。如果此時(shí)圖中尚有頂點(diǎn)未被訪問，則需要另選一個(gè)未曾被訪問過的頂點(diǎn)作為新的起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。

3.2 算法特點(diǎn)

廣度優(yōu)先搜索類似于樹的層次遍歷，是按照一種由近及遠(yuǎn)的方式訪問圖的頂點(diǎn)。在進(jìn)行廣度優(yōu)先搜索時(shí)需要使用隊(duì)列存儲(chǔ)頂點(diǎn)信息。

3.3 圖解過程

3.3.1 無向圖的廣度優(yōu)先搜索

例如：圖3.3.1.1所示的無向圖，采用廣度優(yōu)先搜索過程。

圖3.3.1.1

（1）選取A為起始點(diǎn)，輸出A，A入隊(duì)列，標(biāo)記A，當(dāng)前位置指向A。

（2）隊(duì)列頭為A，A出隊(duì)列。A的鄰接頂點(diǎn)有B、E，輸出B和E，將B和E入隊(duì)，并標(biāo)記B、E。當(dāng)前位置指向A。

（3）隊(duì)列頭為B，B出隊(duì)列。B的鄰接頂點(diǎn)有C、D，輸出C、D，將C、D入隊(duì)列，并標(biāo)記C、D。當(dāng)前位置指向B。

（4）隊(duì)列頭為E，E出隊(duì)列。E的鄰接頂點(diǎn)有D、F，但是D已經(jīng)被標(biāo)記，因此輸出F，將F入隊(duì)列，并標(biāo)記F。當(dāng)前位置指向E。

（5）隊(duì)列頭為C，C出隊(duì)列。C的鄰接頂點(diǎn)有B、D，但B、D均被標(biāo)記。無元素入隊(duì)列。當(dāng)前位置指向C。

（6）隊(duì)列頭為D，D出隊(duì)列。D的鄰接頂點(diǎn)有B、C、E，但是B、C、E均被標(biāo)記，無元素入隊(duì)列。當(dāng)前位置指向D。

（7）隊(duì)列頭為F，F(xiàn)出隊(duì)列。F的鄰接頂點(diǎn)有G、H，輸出G、H，將G、H入隊(duì)列，并標(biāo)記G、H。當(dāng)前位置指向F。

（8）隊(duì)列頭為G，G出隊(duì)列。G的鄰接頂點(diǎn)有F，但F已被標(biāo)記，無元素入隊(duì)列。當(dāng)前位置指向G。

（9）隊(duì)列頭為H，H出隊(duì)列。H的鄰接頂點(diǎn)有F，但F已被標(biāo)記，無元素入隊(duì)列。當(dāng)前位置指向H。

img

（10）隊(duì)列空，則以A為起始點(diǎn)的遍歷結(jié)束。若圖中仍有未被訪問的頂點(diǎn)，則選取未訪問的頂點(diǎn)為起始點(diǎn)，繼續(xù)執(zhí)行此過程。直至所有頂點(diǎn)均被訪問。

3.3.2 有向圖的廣度優(yōu)先搜索

以圖3.3.2.1所示的有向圖為例進(jìn)行廣度優(yōu)先搜索。

圖3.3.2.1

（1）選取A為起始點(diǎn)，輸出A，將A入隊(duì)列，標(biāo)記A。

（2）隊(duì)列頭為A，A出隊(duì)列。以A為尾的邊有兩條，對應(yīng)的頭分別為B、C，則A的鄰接頂點(diǎn)有B、C。輸出B、C，將B、C入隊(duì)列，并標(biāo)記B、C。

（3）隊(duì)列頭為B，B出隊(duì)列。B的鄰接頂點(diǎn)為C，C已經(jīng)被標(biāo)記，因此無新元素入隊(duì)列。

（4）隊(duì)列頭為C，C出隊(duì)列。C的鄰接頂點(diǎn)有E、F。輸出E、F，將E、F入隊(duì)列，并標(biāo)記E、F。

（5）隊(duì)列頭為E，E出隊(duì)列。E的鄰接頂點(diǎn)有G、H。輸出G、H，將G、H入隊(duì)列，并標(biāo)記G、H。

（6）隊(duì)列頭為F，F(xiàn)出隊(duì)列。F無鄰接頂點(diǎn)。

（7）隊(duì)列頭為G，G出隊(duì)列。G無鄰接頂點(diǎn)。

（8）隊(duì)列頭為H，H出隊(duì)列。H鄰接頂點(diǎn)為E，但是E已被標(biāo)記，無新元素入隊(duì)列。

（9）隊(duì)列為空，以A為起始點(diǎn)的遍歷過程結(jié)束，此時(shí)圖中仍有D未被訪問，則以D為起始點(diǎn)繼續(xù)遍歷。選取D為起始點(diǎn)，輸出D，將D入隊(duì)列，標(biāo)記D。

（10）隊(duì)列頭為D，D出隊(duì)列，D的鄰接頂點(diǎn)為B，B已被標(biāo)記，無新元素入隊(duì)列。

（11）隊(duì)列為空，且所有元素均被訪問，廣度優(yōu)先搜索遍歷過程結(jié)束。廣度優(yōu)先搜索的輸出序列為：A->B->E->C->D->F->G->H。

3.4 算法分析

假設(shè)圖有V個(gè)頂點(diǎn)，E條邊，廣度優(yōu)先搜索算法需要搜索V個(gè)節(jié)點(diǎn)，時(shí)間消耗是O(V)，在搜索過程中，又需要根據(jù)邊來增加隊(duì)列的長度，于是這里需要消耗O(E)，總得來說，效率大約是O(V+E)。

4 總結(jié)

圖的遍歷主要就是這兩種遍歷思想，深度優(yōu)先搜索使用遞歸方式，需要棧結(jié)構(gòu)輔助實(shí)現(xiàn)。廣度優(yōu)先搜索需要使用隊(duì)列結(jié)構(gòu)輔助實(shí)現(xiàn)。在遍歷過程中可以看出，對于連通圖，從圖的任意一個(gè)頂點(diǎn)開始深度或廣度優(yōu)先遍歷一定可以訪問圖中的所有頂點(diǎn)，但對于非連通圖，從圖的任意一個(gè)頂點(diǎn)開始深度或廣度優(yōu)先遍歷并不能訪問圖中的所有頂點(diǎn)。