深度優先搜尋演算法（英語：Depth-First-Search，DFS）是一種用於遍歷或搜尋樹或圖的演算法。

這個演算法會儘可能深的搜尋樹的分支。

當節點v的所在邊都己被探尋過，搜尋 ... 深度優先搜尋維基百科，自由的百科全書跳至導覽跳至搜尋深度優先搜尋節點進行深度優先搜尋的順序概況類別搜尋演算法資料結構圖複雜度平均時間複雜度 O ( b m ) {\displaystyleO(b^{m})} 空間複雜度 O ( b m ) {\displaystyleO(bm)} 最佳解否完全性是相關變數的定義 b {\displaystyleb} 分支係數 m {\displaystylem} 圖的最大深度圖與樹搜尋演算法 α–β A* B*（英語：B*）回溯集束（英語：Beamsearch）貝爾曼-福特最佳優先（英語：Best-firstsearch）雙向 Borůvka（英語：Borůvka'salgorithm）分支限界（英語：Branchandbound） BFS 大英博物館 D*（英語：D*） DFS 深度限制（英語：Depth-limitedsearch）迪傑斯特拉 Edmonds（英語：Edmonds'algorithm）弗洛伊德邊緣搜尋爬山 IDA*（英語：IterativedeepeningA*）迭代加深 Johnson（英語：Johnson'salgorithm）跳點（英語：Jumppointsearch）克魯斯克爾詞典BFS（英語：Lexicographicbreadth-firstsearch） LPA*（英語：LifelongPlanningA*）普里姆 SMA*（英語：SMA*）最短路徑快速分類圖演算法搜尋演算法演算法列表（英語：Listofalgorithms）相關主題動態規劃圖的遍歷樹的遍歷閱論編深度優先搜尋演算法（英語：Depth-First-Search，DFS）是一種用於遍歷或搜尋樹或圖的演算法。

這個演算法會儘可能深的搜尋樹的分支。

當節點v的所在邊都己被探尋過，搜尋將回溯到發現節點v的那條邊的起始節點。

這一過程一直進行到已發現從源節點可達的所有節點為止。

如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個行程反覆進行直到所有節點都被存取為止。

[1]（p.603）這種演算法不會根據圖的結構等資訊調整執行策略[來源請求]。

深度優先搜尋是圖論中的經典演算法，利用深度優先搜尋演算法可以產生目標圖的拓撲排序表[1]（p.612），利用拓撲排序表可以方便的解決很多相關的圖論問題，如無權最長路徑問題等等。

因發明「深度優先搜尋演算法」，約翰·霍普克洛夫特與羅伯特·塔揚在1986年共同獲得電腦領域的最高獎：圖靈獎。

[2] 目次 1演算方法 2C++的實作 3參考文獻 4參見演算方法[編輯] 首先將根節點放入stack中。

從stack中取出第一個節點，並檢驗它是否為目標。

如果找到目標，則結束搜尋並回傳結果。

否則將它某一個尚未檢驗過的直接子節點加入stack中。

重複步驟2。

如果不存在未檢測過的直接子節點。

將上一級節點加入stack中。

重複步驟2。

重複步驟4。

若stack為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。

結束搜尋並回傳「找不到目標」。

C++的實作[編輯] 定義一個結構體來表達一個二元樹的節點的結構： structNode{ intself;//数据 Node*left;//左孩子 Node*right;//右孩子 }; 那麼我們在搜尋一個樹的時候，從一個節點開始，能首先取得的是它的兩個子節點。

例如： “ A BC DEFG ” A是第一個存取的，然後順序是B和D、然後是E。

然後再是C、F、G。

那麼我們怎麼來保證這個順序呢？這裡就應該用堆疊的結構，因為堆疊是一個後進先出(LIFO)的順序。

通過使用C++的STL，下面的程式能幫助理解： constintTREE_SIZE=9; std::stackunvisited; Nodenodes[TREE_SIZE]; Node*current; //初始化树 for(inti=0;iright!=NULL) unvisited.push(current->right); if(current->left!=NULL) unvisited.push(current->left); cout<self<