一、圖的遍歷

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

前面已經(jīng)講過了二叉樹的節(jié)點(diǎn)遍歷。

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

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

• 深度優(yōu)先搜索
• 廣度優(yōu)先搜索

二、深度優(yōu)先搜索（DFS，Depth First Search）

深度優(yōu)先搜索，從起點(diǎn)出發(fā)，從規(guī)定的方向中選擇其中一個(gè)不斷地向前走，直到無法繼續(xù)為止，然后嘗 試另外一種方向，直到最后走到終點(diǎn)。就像走迷宮一樣，盡量往深處走。

DFS 解決的是連通性的問題，即，給定兩個(gè)點(diǎn)，一個(gè)是起始點(diǎn)，一個(gè)是終點(diǎn)，判斷是不是有一條路徑能 從起點(diǎn)連接到終點(diǎn)。起點(diǎn)和終點(diǎn)，也可以指的是某種起始狀態(tài)和最終的狀態(tài)。問題的要求并不在乎路徑 是長(zhǎng)還是短，只在乎有還是沒有。

假設(shè)我們有這么一個(gè)圖，里面有A、B、C、D、E、F、G、H 8 個(gè)頂點(diǎn)，點(diǎn)和點(diǎn)之間的聯(lián)系如下圖所示， 對(duì)這個(gè)圖進(jìn)行深度優(yōu)先的遍歷。

必須依賴棧（Stack），特點(diǎn)是后進(jìn)先出（LIFO）。

第一步，選擇一個(gè)起始頂點(diǎn)，例如從頂點(diǎn) A 開始。把 A 壓入棧，標(biāo)記它為訪問過（用紅色標(biāo)記），并輸 出到結(jié)果中。

第二步，尋找與 A 相連并且還沒有被訪問過的頂點(diǎn)，頂點(diǎn) A 與 B、D、G 相連，而且它們都還沒有被訪 問過，我們按照字母順序處理，所以將 B 壓入棧，標(biāo)記它為訪問過，并輸出到結(jié)果中。

第三步，現(xiàn)在我們?cè)陧旤c(diǎn) B 上，重復(fù)上面的操作，由于 B 與 A、E、F 相連，如果按照字母順序處理的 話，A 應(yīng)該是要被訪問的，但是 A 已經(jīng)被訪問了，所以我們?cè)L問頂點(diǎn) E，將 E 壓入棧，標(biāo)記它為訪問 過，并輸出到結(jié)果中。

第四步，從 E 開始，E 與 B、G 相連，但是B剛剛被訪問過了，所以下一個(gè)被訪問的將是G，把G壓入 棧，標(biāo)記它為訪問過，并輸出到結(jié)果中。

第五步，現(xiàn)在我們?cè)陧旤c(diǎn) G 的位置，由于與 G 相連的頂點(diǎn)都被訪問過了，類似于我們走到了一個(gè)死胡 同，必須嘗試其他的路口了。所以我們這里要做的就是簡(jiǎn)單地將 G 從棧里彈出，表示我們從 G 這里已 經(jīng)無法繼續(xù)走下去了，看看能不能從前一個(gè)路口找到出路。

如果發(fā)現(xiàn)周圍的頂點(diǎn)都被訪問了，就把當(dāng)前的頂點(diǎn)彈出。

第六步，現(xiàn)在棧的頂部記錄的是頂點(diǎn) E，我們來看看與 E 相連的頂點(diǎn)中有沒有還沒被訪問到的，發(fā)現(xiàn)它 們都被訪問了，所以把 E 也彈出去。

第七步，當(dāng)前棧的頂點(diǎn)是 B，看看它周圍有沒有還沒被訪問的頂點(diǎn)，有，是頂點(diǎn) F，于是把 F 壓入棧， 標(biāo)記它為訪問過，并輸出到結(jié)果中。

第八步，當(dāng)前頂點(diǎn)是 F，與 F 相連并且還未被訪問到的點(diǎn)是 C 和 D，按照字母順序來，下一個(gè)被訪問的 點(diǎn)是 C，將 C 壓入棧，標(biāo)記為訪問過，輸出到結(jié)果中。

第九步，當(dāng)前頂點(diǎn)為 C，與 C 相連并尚未被訪問到的頂點(diǎn)是 H，將 H 壓入棧，標(biāo)記為訪問過，輸出到結(jié) 果中。

第十步，當(dāng)前頂點(diǎn)是 H，由于和它相連的點(diǎn)都被訪問過了，將它彈出棧。

第十一步，當(dāng)前頂點(diǎn)是 C，與 C 相連的點(diǎn)都被訪問過了，將 C 彈出棧。

第十二步，當(dāng)前頂點(diǎn)是 F，與 F 相連的并且尚未訪問的點(diǎn)是 D，將 D 壓入棧，輸出到結(jié)果中，并標(biāo)記為訪問過。

第十三步，當(dāng)前頂點(diǎn)是 D，與它相連的點(diǎn)都被訪問過了，將它彈出棧。以此類推，頂點(diǎn) F，B，A 的鄰居 都被訪問過了，將它們依次彈出棧就好了。最后，當(dāng)棧里已經(jīng)沒有頂點(diǎn)需要處理了，我們的整個(gè)遍歷結(jié)束。

三、時(shí)間復(fù)雜度

鄰接表 訪問所有頂點(diǎn)的時(shí)間為 O(V)，而查找所有頂點(diǎn)的鄰居一共需要 O(E) 的時(shí)間，所以總的時(shí)間復(fù)雜度是 O(V + E)。

鄰接矩陣 查找每個(gè)頂點(diǎn)的鄰居需要 O(V) 的時(shí)間，所以查找整個(gè)矩陣的時(shí)候需要 O( V * V) 的時(shí)間。