一、圖的遍歷

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

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

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

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

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

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

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

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

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

必須依賴棧（Stack），特點是后進先出（LIFO）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、時間復(fù)雜度

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

鄰接矩陣 查找每個頂點的鄰居需要 O(V) 的時間，所以查找整個矩陣的時候需要 O( V * V) 的時間。