深度優先搜尋
深度優先搜尋演算法（英語：Depth-First-Search，縮寫為DFS）是一種用於遍歷或搜尋樹或圖的演算法。這個演算法會儘可能深地搜尋樹的分支。當節點v的所在邊都己被探尋過，搜尋將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個行程反覆進行直到所有節點都被訪問為止。[1]（p. 603）這種演算法不會根據圖的結構等資訊調整執行策略[來源請求]。
| 深度優先搜尋 | |
|---|---|
 節點進行深度優先搜尋的順序 | |
| 概況 | |
| 類別 | 搜尋演算法 |
| 資料結構 | 圖 |
| 複雜度 | |
| 平均時間複雜度 | |
| 空間複雜度 | |
| 最佳解 | 否 |
| 完全性 | 是 |
| 相關變數的定義 | |
| 分支係數 | |
| 圖的最大深度 | |
深度優先搜尋是圖論中的經典演算法，利用深度優先搜尋演算法可以產生目標圖的拓撲排序表[1]（p. 612），利用拓撲排序表可以方便的解決很多相關的圖論問題，如無權最長路徑問題等等。
演算方法
- 首先將根節點放入stack中。
- 從stack中取出第一個節點，並檢驗它是否為目標。
- 如果找到目標，則結束搜尋並回傳結果。
- 否則將它某一個尚未檢驗過的直接子節點加入stack中。
- 重複步驟2。
- 如果不存在未檢測過的直接子節點。
- 將上一級節點加入stack中。
- 重複步驟2。
- 重複步驟4。
- 若stack為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標。結束搜尋並回傳「找不到目標」。
C++的實作
定義一個結構體來表達一個二元樹的節點的結構：
struct Node {
int self; // 数据
Node *left; // 左孩子
Node *right; // 右孩子
};
那麼我們在搜尋一個樹的時候，從一個節點開始，能首先取得的是它的兩個子節點。例如：
| “ |
A
B C
D E F G
|
” |
A是第一個訪問的，然後順序是B和D、然後是E。然後再是C、F、G。那麼我們怎麼來保證這個順序呢？
這裡就應該用堆疊的結構，因為堆疊是一個後進先出(LIFO)的順序。通過使用C++的STL，下面的程式能幫助理解：
const int TREE_SIZE = 9;
std::stack<Node *> unvisited;
Node nodes[TREE_SIZE];
Node *current;
//初始化树
for (int i = 0; i < TREE_SIZE; i++) {
nodes[i].self = i;
int child = i * 2 + 1;
if (child < TREE_SIZE) // Left child
nodes[i].left = &nodes[child];
else
nodes[i].left = NULL;
child++;
if (child < TREE_SIZE) // Right child
nodes[i].right = &nodes[child];
else
nodes[i].right = NULL;
}
unvisited.push(&nodes[0]); //先把0放入UNVISITED stack
// 树的深度优先搜索在二叉树的特例下，就是二叉树的先序遍历操作（这里是使用循环实现）
// 只有UNVISITED不空
while (!unvisited.empty()) {
current = (unvisited.top()); //当前访问的
unvisited.pop();
if (current->right != NULL)
unvisited.push(current->right );
if (current->left != NULL)
unvisited.push(current->left);
cout << current->self << endl;
}
參考文獻
- ^ 1.0 1.1 Introduction to Algorithms [演算法導論]. ISBN 978-7-111-40701-0.
- ^ Robert E Tarjan - A.M. Turing Award Winner. [2017-10-29]. （原始內容存檔於2017-10-30） （英語）.