DFS(深度優先搜尋)

深度優先搜尋算法（Depth-First-Search），是搜尋算法的一種。它沿着樹的深度周遊樹的節點，盡可能深的搜尋樹的分支。當節點v的所有邊都己被探尋過，搜尋将回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點， 則選擇其中一個作為源節點并重複以上過程，整個程序反複進行直到所有節點都被通路為止。DFS屬于盲目搜尋。

深度優先搜尋是圖論中的經典算法，利用深度優先搜尋算法可以産生目标圖的相應拓撲排序表，利用拓撲排序表可以友善的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆資料結構來輔助實作DFS算法。

深度優先周遊圖算法步驟：

1. 通路頂點v；

2. 依次從v的未被通路的鄰接點出發，對圖進行深度優先周遊；直至圖中和v有路徑相通的頂點都被通路；

3. 若此時圖中尚有頂點未被通路，則從一個未被通路的頂點出發，重新進行深度優先周遊，直到圖中所有頂點均被通路過為止。

上述描述可能比較抽象，舉個執行個體：

DFS 在通路圖中某一起始頂點 v 後，由 v 出發，通路它的任一鄰接頂點 w1；再從 w1 出發，通路與 w1 鄰接但還沒有通路過的頂點 w2；然後再從 w2 出發，進行類似的通路，… 如此進行下去，直至到達所有的鄰接頂點都被通路過的頂點 u 為止。接着，退回一步，退到前一次剛通路過的頂點，看是否還有其它沒有被通路的鄰接頂點。如果有，則通路此頂點，之後再從此頂點出發，進行與前述類似的通路；如果沒有，就再退回一步進行搜尋。重複上述過程，直到連通圖中所有頂點都被通路過為止。