Depth-first search (DFS) is an algorithm for traversing or searching a tree, ... 深度優先搜尋法，是一種用來遍尋一個樹(tree)或圖(graph)的演算法。

關於童玩.程式.老玩童九連環智慧拼盤華容道資料結構與演算法疊代與遞廻回溯法深度優先搜尋法廣度優先搜尋法遊戲超級運動員 Contact 深度優先搜尋法 (Depth-firstSearch) Depth-firstsearch(DFS)isanalgorithmfor traversingorsearchingatree,treestructure,orgraph.Onestartsat theroot(selectingsomenodeastherootinthegraphcase)and exploresasfaraspossible alongeachbranchbeforebacktracking. (參1) 深度優先搜尋法，是一種用來遍尋一個樹(tree)或圖(graph)的演算法。

由樹的根(或圖的某一點當成根)來開始探尋，先探尋邊(edge)上未搜尋的一節點(vertexor node)，並儘可能深的搜索，直到該節點的所有邊上節點都已探尋；就回溯(backtracking)到前一個節點，重覆探尋未搜尋的節點，直到找到目的節點或遍尋全部節點。

深度優先搜尋法屬於盲目搜索(uninformedsearch)是利用堆疊(Stack)來處理，通常以遞迴的方式呈現。

(參2) 樹與圖樹是圖的一種特例，關於樹與圖請參考:樹-wiki(參3) 或樹-演算法筆記(參4),圖-wiki(參5) 或圖-演算法筆記(參6) 範例:以深度優先搜尋法找出下圖的所有節點順序:        假設起始點為A，且每一節點由左至右的順序來搜尋下個節點，則結果為:A,B,E,F,D,C,G 演算法    proceduredfs(vertexv) {    markvasvisited    foreachwadjacenttov{       ifwunvisited{          dfs(w)        }    } } 範例:以深度優先搜尋法繪製一個迷宮        將迷宮看成如棋盤由一個個方格(cell) 所組成，每個方格由4面牆所圍著(圖1)，一開始任取其中一個方格為起始點，由此方格任意取相鄰且未走過的方格為下個位置，並將兩個方格中間的牆壁移除，再由下個位置任意取相鄰且未走過的方格往下走，如此重覆直到相鄰位置均已走過，即為死路(dead-end)。

當遇到死路後要退回 (backtracking)到上一個方格，再由此位置取相鄰且未走過的繼續往下走，如此重覆，最後會回溯到起始點，且走完全部方格，此即為一迷宮(圖 2)。

(參7) 圖1 圖2        我們可將迷宮視為一個圖(graph)，方格看成節點(vertex)，相鄰的牆即為邊(edge)(圖3)，而迷宮的完成可看成由圖隨意產生出的生成樹(SpanningTree參8)(圖4)，而樹的任意兩節點只有一種路徑可以到達，所以任取兩方格為起點及終點即形成單一路徑的迷宮。

Graph圖3 SpanningTree圖4 完整迷宮繪製: 繪製迷宮(JavaScript) 範例:以深度優先搜尋法找出迷宮出口        由所繪製的迷宮取任兩點為起點及終點即形成單一路徑的迷宮，以深度優先搜尋法找出迷宮出口，其方法跟繪製迷宮相同，因為是盲目搜索(uninformedsearch)所以有時即使已接近出口還是會繞一大圏才會找到。

迷宮找出口(JavaScript) 參考資料:        (1)Depth-firstsearchwiki:http://en.wikipedia.org/wiki/Depth-first_search        (2)縱向優先搜尋(depth-firstsearch):http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/dfs.html        (3)Tree(graphtheory)wiki:http://en.wikipedia.org/wiki/Tree_(graph_theory)        (4)Tree(演算法筆記):http://www.csie.ntnu.edu.tw/~u91029/Tree.html        (5)Graph(mathematics)wiki:http://en.wikipedia.org/wiki/Graph_(mathematics)        (6)Graph(演算法筆記):http://www.csie.ntnu.edu.tw/~u91029/Graph.html        (7)Mazegenerationalgorithmwiki:http://en.wikipedia.org/wiki/Maze_generation_algorithm        (8)SpanningTree(演算法筆記):http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html 如有版權問題，請告知。