深度優先搜揣

深度優先搜揣演算法（英語：Depth-First-Search，DFS）是一種用佇遍歷抑是搜尋樹仔抑是圖的演算法。這个演算法會冗早深的所在揣樹仔的分支。做節點 v 的所在邊攏去予人探揣過，搜揣欲回溯到發現節點 v 的彼條邊的起始節點。這个過程一直進行到已經發現對源節點會當到的所有節點為止。若猶閣存在無去予人發現的節點，則選擇其中一个作為源節點並重複以上的過程，規个行程重複進行一直到所有的點攏予人儉取做止。這款的演算法袂根據圖的結構等資訊調整執行策略。

深度優先搜揣是圖論中的經典演算法，利用深度優先搜揣演算法會當產生目標圖的拓撲排序表，利用拓撲排序表會當方便解決真濟相關的圖論問題，如無權上長路徑問題等等。

因發明「深度優先搜揣演算法」，約翰 ・ 霍普克洛夫特佮羅伯特 ・ 塔揚佇一九八六年共同得著電腦領域的上懸獎：圖靈獎。

演算方法

一 . 首先共根節點囥入去 stack 中。 二 . 對 stack 中取出第一个節點，而且檢驗伊敢是目標。

若揣著目標，結束搜揣並回傳結果。

若無共伊某一个猶未檢驗過的直接子節點加入 stack 中。

三 . 重複步數字。 四 . 若是無存在無檢測過直接子節點。

共頂一級節點加入 stack 中。

重複步數字。

五 . 重複步數四。 六 . 若是 stack 為空，表示規張圖攏檢查過矣—— 亦即圖當中伊無欲走揣的目標。結束搜揣並回傳「揣無目標」。

C + + 的實作

定義一个結構體來表達一个二箍樹的節點的結構：

若按呢咱咧走揣一个樹仔的時陣，佇一个節點開始，會當代先取得的是伊的兩个子節點。比如講：

A 是第一个存取的，然後順序是 B 和 D、然後是 E。閣再來 C、F、G。按呢咱按怎來保證這个順序咧？

遮就應該用疊起來的結構，因為疊一个是後進先出 ( LIFO ) 的順序。通過使用 C + + 的 STL，下跤的程式會當幫助理解：

參見

• 闊度優先搜揣