深度優先搜索

深度優先搜索
節點搜索的順序 節點進行深度優先搜索的順序
概況
類別	搜索演算法
資料結構	圖
複雜度
平均時間複雜度	$O(b^{m})$
空間複雜度	$O(bm)$
最佳解	否
完全性	是
相關變量的定義
$b$	分支係數
$m$	圖的最大深度

深度優先搜索算法（英語：Depth-First-Search，縮寫為DFS）是一種用於遍歷或搜索樹或圖的算法。這個算法會儘可能深地搜索樹的分支。當節點v的所在邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重複以上過程，整個進程反覆進行直到所有節點都被訪問為止。這種算法不會根據圖的結構等信息調整執行策略。

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

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

演算方法

1. 首先將根節點放入stack中。
2. 從stack中取出第一個節點，並檢驗它是否為目標。

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

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

3. 重複步驟2。
4. 如果不存在未檢測過的直接子節點。

   將上一級節點加入stack中。

   重複步驟2。

5. 重複步驟4。
6. 若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;
}

參見

• 廣度優先搜索