前言

圖是一種靈活的數(shù)據(jù)結(jié)構(gòu)，一般作為一種模型用來定義對象之間的關(guān)系或聯(lián)系。對象由頂點（V）表示，而對象之間的關(guān)系或者關(guān)聯(lián)則通過圖的邊（E）來表示。
圖可以分為有向圖和無向圖，一般用G=(V,E)來表示圖。經(jīng)常用鄰接矩陣或者鄰接表來描述一副圖。
在圖的基本算法中，最初需要接觸的就是圖的遍歷算法。

根據(jù)訪問節(jié)點的順序，可分為廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）。

---

正文

廣度優(yōu)先搜索（BFS）

廣度優(yōu)先搜索在進(jìn)一步遍歷圖中頂點之前，先訪問當(dāng)前頂點的所有鄰接結(jié)點。
a .首先選擇一個頂點作為起始結(jié)點，并將其染成灰色，其余結(jié)點為白色。
b. 將起始結(jié)點放入隊列中。
c. 從隊列首部選出一個頂點，并找出所有與之鄰接的結(jié)點，將找到的鄰接結(jié)點放入隊列尾部，將已訪問過結(jié)點涂成黑色，沒訪問過的結(jié)點是白色。如果頂點的顏色是灰色，表示已經(jīng)發(fā)現(xiàn)并且放入了隊列，如果頂點的顏色是白色，表示還沒有發(fā)現(xiàn)
d. 按照同樣的方法處理隊列中的下一個結(jié)點。
基本就是出隊的頂點變成黑色，在隊列里的是灰色，還沒入隊的是白色。
用一副圖來表達(dá)這個流程如下：

1.初始狀態(tài)，從頂點1開始，隊列={1}

2.訪問1的鄰接頂點，1出隊變黑，2,3入隊，隊列={2,3,}

3.訪問2的鄰接結(jié)點，2出隊，4入隊，隊列={3,4}

4.訪問3的鄰接結(jié)點，3出隊，隊列={4}

5.訪問4的鄰接結(jié)點，4出隊，隊列={ 空}

從頂點1開始進(jìn)行廣度優(yōu)先搜索：

?

初始狀態(tài)，從頂點1開始，隊列={1}

訪問1的鄰接頂點，1出隊變黑，2,3入隊，隊列={2,3,}

訪問2的鄰接結(jié)點，2出隊，4入隊，隊列={3,4}

訪問3的鄰接結(jié)點，3出隊，隊列={4}

訪問4的鄰接結(jié)點，4出隊，隊列={ 空}
結(jié)點5對于1來說不可達(dá)。

上面的圖可以通過如下鄰接矩陣表示：

int maze[5][5] = { { 0, 1, 1, 0, 0 }, { 0, 0, 1, 1, 0 }, { 0, 1, 1, 1, 0 }, { 1, 0, 0, 0, 0 }, { 0, 0, 1, 1, 0 }};

BFS核心代碼如下：

---

深度優(yōu)先搜索（DFS）

深度優(yōu)先搜索在搜索過程中訪問某個頂點后，需要遞歸地訪問此頂點的所有未訪問過的相鄰頂點。
初始條件下所有節(jié)點為白色，選擇一個作為起始頂點，按照如下步驟遍歷：
a. 選擇起始頂點涂成灰色，表示還未訪問
b. 從該頂點的鄰接頂點中選擇一個，繼續(xù)這個過程（即再尋找鄰接結(jié)點的鄰接結(jié)點），一直深入下去，直到一個頂點沒有鄰接結(jié)點了，涂黑它，表示訪問過了
c. 回溯到這個涂黑頂點的上一層頂點，再找這個上一層頂點的其余鄰接結(jié)點，繼續(xù)如上操作，如果所有鄰接結(jié)點往下都訪問過了，就把自己涂黑，再回溯到更上一層。
d. 上一層繼續(xù)做如上操作，直到所有頂點都訪問過。
用圖可以更清楚的表達(dá)這個過程：

1.初始狀態(tài)，從頂點1開始

?

2.依次訪問過頂點1,2,3后，終止于頂點3

?

3.從頂點3回溯到頂點2，繼續(xù)訪問頂點5，并且終止于頂點5

?

4.從頂點5回溯到頂點2，并且終止于頂點2

?

5.從頂點2回溯到頂點1，并終止于頂點1

?

6.從頂點4開始訪問，并終止于頂點4

從頂點1開始做深度搜索：

?

初始狀態(tài)，從頂點1開始

依次訪問過頂點1,2,3后，終止于頂點3

從頂點3回溯到頂點2，繼續(xù)訪問頂點5，并且終止于頂點5

從頂點5回溯到頂點2，并且終止于頂點2

從頂點2回溯到頂點1，并終止于頂點1

從頂點4開始訪問，并終止于頂點4

上面的圖可以通過如下鄰接矩陣表示：

int maze[5][5] = { { 0, 1, 1, 0, 0 }, { 0, 0, 1, 0, 1 }, { 0, 0, 1, 0, 0 }, { 1, 1, 0, 0, 1 }, { 0, 0, 1, 0, 0 }};

遞歸版本

非遞歸版本，借助一個棧：

有的DFS是先訪問讀取到的結(jié)點，等回溯時就不再輸出該結(jié)點，也是可以的。算法和我上面的區(qū)別就是輸出點的時機不同，思想還是一樣的。DFS在環(huán)監(jiān)測和拓?fù)渑判蛑卸加胁诲e的應(yīng)用。

一句話：

BFS就是維護(hù)一個隊列，先依次訪問起始點相鄰的節(jié)點，入隊，再訪問相鄰節(jié)點的相鄰節(jié)點，依次入隊出隊。

DFS就是利用遞歸+回溯，直到遞歸到?jīng)]有相鄰節(jié)點可以訪問了，就向上回溯。

總結(jié)

以上是生活随笔為你收集整理的图的遍历：BFS和DFS的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。