圖論深度優先搜尋
推出一個新系列，《看圖輕鬆理解資料結構和演算法》，主要使用圖片來描述常見的資料結構和演算法，輕鬆閱讀並理解掌握。本系列包括各種堆、各種佇列、各種列表、各種樹、各種圖、各種排序等等幾十篇的樣子。
關於圖遍歷
圖遍歷即圖的遍歷，指從圖中任一頂點出發，對圖中的所有頂點訪問一次。圖的遍歷與樹的遍歷相似，但圖的結構更加複雜，比如要考慮迴路的情況。圖的遍歷操作是一種基本操作，很多其他操作都建立在圖遍歷基礎之上。圖的遍歷演算法主要有廣度優先搜尋和深度優先搜尋，這裡看深度優先搜尋。
深度優先搜尋
深度優先搜尋(Depth First Search)，簡稱DFS。簡單來說，深度優先搜尋就是對每一個可能的分支深入到不能在深入為止，且每個頂點只能訪問一次。DFS的時間複雜度為 $O(|V|+|E|)$ ，其中 $|V|$ 為圖的頂點數， $|E|$ 為圖的邊數。
核心思想
- 選擇一個初始頂點，並將其標記為已訪問；
- 若當前頂點存在未被訪問過的鄰接頂點，則任選一個頂點作為下一個頂點，並將下一個頂點標記為已訪問；
- 若當前頂點的所有鄰接頂點都已被訪問過，則回退到最近一次訪問的頂點；
- 不斷執行步驟2和步驟3，直到與起始頂點相通的全部頂點都訪問完畢；
- 如果圖中的頂點還有未被訪問的，則再選出其中一個頂點作為起始頂點，繼續執行步驟2到步驟4；
- 遍歷結束。
搜尋過程
在實現深度優先搜尋的過程中需要用到一個棧和一個數組，棧用於儲存所有待檢測的頂點，而陣列用於標識哪些頂點已被訪問，F表示未被訪問，T表示已被訪問。
對於一個擁有8個頂點的無向加權圖，分別用0-7來表示圖的每個頂點，因為遍歷與邊的權重無關，這裡將權重值省略。
選擇3作為初始頂點，將其推入棧中，棧頂的元素即是當前檢測的頂點，並將陣列對應元素標為T。
從頂點3開始，選擇一條邊進行檢測，選擇到達頂點1的邊，
因為頂點1的訪問標記為F，說明還未被訪問過，於是將1推入BFS棧中，同時將訪問標記改為T。
此時棧頂元素為1，繼續從頂點1選擇一條邊進行檢測，選擇到達頂點0的邊，
因為頂點0的訪問標記為F，說明還未被訪問過，於是將0推入BFS棧中，同時將訪問標記改為T。
此時棧頂的元素為0，繼續從頂點0選擇一條邊進行檢測，選擇到達頂點1的邊，因為訪問標記為T，說明已經被訪問過，所以訪問標記和DFS棧都不更新。
繼續從頂點0選擇一條邊進行檢測，選擇到達頂點2的邊，
因為頂點2的訪問標記為F，說明還未被訪問過，於是將2推入BFS棧中，同時將訪問標記改為T。
此時棧頂的元素為2，繼續從頂點2選擇一條邊進行檢測，選擇到達頂點0的邊，因為訪問標記為T，說明已經被訪問過，所以訪問標記和DFS棧都不更新。
繼續從頂點2選擇一條邊進行檢測，選擇到達頂點1的邊，因為訪問標記為T，說明已經被訪問過，所以訪問標記和DFS棧都不更新。
此時頂點2的所有邊都已經檢查完，已經無法繼續深入，所以對頂點2進行出棧操作。然後棧頂元素為0，
對於頂點0，頂點2和頂點1的邊之前都已經檢測過了，已經不存在未訪問的邊，所以直接對頂點0進行出棧操作。然後棧頂元素為1，
繼續從頂點1選擇一條未訪問的邊進行檢測，前面檢測頂點1時我們是選擇了往頂點0的邊，所以還剩下頂點2和頂點3未訪問過，分別對它們進行檢測，發現訪問標記都為T，說明已經被訪問過，所以訪問標記和DFS棧都不更新。
此時頂點1的所有邊都已經檢查完，對頂點1進行出棧操作。然後棧頂元素為3，
繼續從頂點3選擇一條未訪問的邊進行檢測，前面檢測頂點3時我們是選擇了往頂點1的邊，所以還剩下頂點4和頂點5未訪問過，這次選擇頂點4的邊。
因為頂點4的訪問標記為F，說明還未被訪問過，於是將4推入BFS棧中，同時將訪問標記改為T。
此時棧頂元素為4，從頂點4選擇一條邊進行檢測，選擇到達頂點3的邊，因為訪問標記為T，說明已經被訪問過，所以訪問標記和DFS棧都不更新。
繼續從頂點4選擇一條邊進行檢測，選擇到達頂點6的邊，
因為頂點6的訪問標記為F，說明還未被訪問過，於是將6推入BFS棧中，同時將訪問標記改為T。
此時棧頂元素為6，從頂點6選擇一條邊進行檢測，選擇到達頂點4的邊，因為訪問標記為T，說明已經被訪問過，所以訪問標記和DFS棧都不更新。
繼續從頂點6選擇一條邊進行檢測，選擇到達頂點5的邊，
因為頂點5的訪問標記為F，說明還未被訪問過，於是將5推入BFS棧中，同時將訪問標記改為T。
此時棧頂元素為5，分別檢測頂點5到頂點3和頂點6的邊，發現頂點訪問標記都為T，無法繼續深入，所以對5進行出棧操作，
此時棧頂元素為6，頂點6沒有未訪問過的邊，所以對6進行出棧操作，
此時棧頂元素為4，頂點4到頂點7的邊還未被訪問過，對其進行訪問，
因為頂點7的訪問標記為F，說明還未被訪問過，於是將7推入BFS棧中，同時將訪問標記改為T。
頂點7發現沒辦法繼續深入訪問，於是對7進行出棧操作。
此時棧頂元素為4，頂點4沒有未訪問過的邊，所以對4進行出棧操作，
此時棧頂元素為3，前面處理頂點3時我們已經檢測了頂點1和頂點4的邊，所以這次選擇頂點5的邊。頂點5的訪問標記為T，說明已經被訪問過，所以訪問標記和DFS棧都不更新。
接著發現頂點3所有邊都已經檢測完畢，所以對3進行出棧操作。現在DFS棧內沒有任何元素，所以我們已經完成了整個遍歷過程。
-------------推薦閱讀------------
ofollow,noindex">我的開源專案彙總(機器&深度學習、NLP、網路IO、AIML、mysql協議、chatbot)
我的2017文章彙總——Java及中介軟體
我的2017文章彙總——JDK原始碼篇
跟我交流，向我提問：
Line"/>
歡迎關注：
