Depth-first search (DFS) is an algorithm for
traversing or searching a tree, tree structure, or graph.One starts at
the root (selecting some node as the root in the graph case) and
explores as far as possible along each branch before backtracking.
(
參1)
深度優先搜尋法，是一種用來遍尋一個樹(tree)或圖(graph)的演算法。由樹的根(或圖的某一點當成
根)來開始探尋，先探尋邊(edge)上未搜尋的一節點(vertex or
node)，並儘可能深的搜索，直到該節點的所有邊上節點都已探尋；就回溯(backtracking)到前一個節點，重覆探尋未搜尋的節點，直到找到目
的節點或遍尋全部節點。
深度優先搜尋法屬於盲目搜索(uninformed search)是利用堆疊(Stack)來處理，通常以遞迴的方式呈現。(
參2)
範例: 以深度優先搜尋法找出下圖的所有節點順序:
假設起始點為 A，且每一節點由左至右的順序來搜尋下個節點，則結果為: A, B, E, F, D, C, G
演算法
procedure dfs(vertex v)
{
mark v as visited
for each w adjacent to v {
if w unvisited {
dfs(w)
}
}
}
|
|
範例: 以深度優先搜尋法繪製一個迷宮
將迷宮看成如棋盤由一個個方格(cell)
所組成，每個方格由4面牆所圍著(圖1)，一開始任取其中一個方格為起始點，由此方格任意取相鄰且未走過的方格為下個位置，並將兩個方格中間的牆壁移除，
再由下個位置任意取相鄰且未走過的方格往下走，如此重覆直到相鄰位置均已走過，即為死路(dead-end)。當遇到死路後要退回
(backtracking)到上一個方格，再由此位置取相鄰且未走過的繼續往下走，如此重覆，最後會回溯到起始點，且走完全部方格，此即為一迷宮(圖
2)。
(參7)
圖1
| 
圖2
|
我們可將迷宮視為一個圖(graph)，方格看成節點(vertex) ，相鄰的牆即為邊(edge)(圖3)，而迷宮的完成可看成由圖隨意產生出的生成樹(Spanning Tree參8)(圖4)，而樹的任意兩節點只有一種路徑可以到達，所以任取兩方格為起點及終點即形成單一路徑的迷宮。
Graph 圖3
| 
Spanning Tree 圖4
|
完整迷宮繪製:
繪製迷宮(JavaScript)
範例: 以深度優先搜尋法找出迷宮出口
由所繪製的迷宮取任兩點為起點及終點即形成單一路徑的迷宮，以深度優先搜尋法找出迷宮出口，其方法跟繪製迷宮相同，
因為是盲目搜索(uninformed search)所以有時即使已接近出口還是會繞一大圏才會找到。
