昨天我們看了BFS的走訪方式，今天要來看深度優先搜尋(Depth First Search,DFS)或稱先廣後深搜尋

什麼是深度優先搜尋(DFS)

簡單來說，DFS是從起點出發，先沿著一條路徑一直往下走到底，走不下去了才回頭，換另一條路徑繼續走到底，可以用堆疊(Stack)完成

假設要從 A 點走到 B 點，最直覺的方法可以先選一個方向一直走
這時遇到死路怎麼辦呢 ?
直接退回上一個岔路口，換另一條路再走到底就好

退回上一個岔路口

用二元樹來看的話長這樣

拜訪步驟

用以下例子來解釋 :

從 1 出發，相鄰串列大概長這樣:

• 1: [2, 4]
• 2: [1, 3]
• 3: [2]
• 4: [1, 5, 6]
• 5: [4]
• 6: [4]

這邊選擇節點的優先順序是看鄰接串列最前面的

1. 從 1 出發，標記 1 拜訪過，先選 1 的節點 2 走
   

2. 到 2，訪問，因為 1 已經訪問過，所以選2的子節點 : 3
   

3. 到 3，訪問 3，沒有子節點所以回頭
   
   

4. 回到 2，檢查 2 還有沒有其他子節點，也沒有，繼續回頭
   

5. 回到 1，往 1 另一個子節點 4 走
   
   剩下的概念都以此類推~

6. 到 4，拜訪，選 4 的節點:5

7. 到 5，訪問，5 沒有子節點,回頭

8. 回到 4，檢查 4 還有沒有其他子節點 : 6，往下走

9. 到 6，訪問 ， 6沒有子節點所以回頭

10. 一路回頭，所有節點都拜訪過了,結束

為什麼DFS要用堆疊? 回想堆疊的LIFO特性

DFS是 :「先走到底，遇到死路要退回上一個岔路口」，正好對應到堆疊「後進先出(LIFO)」的特性
最後走過的那個岔路口，要最先被退回去檢查
和 Stack 「最後放進去,最先被拿出來」的邏輯一樣。

回想遞迴呼叫的堆疊 ( Day05 提過的Call Stack )
其實DFS用遞迴寫出來的版本，本質上就是借用了系統自動幫你維護的呼叫堆疊，不需要自己額外宣告一個Stack物件。

用遞迴實作DFS

#include <bits/stdc++.h>

using namespace std;

vector<int> graph[7];
bool visited[7];

void DFS(int cur)
{
    visited[cur] = true;
    cout << cur << " ";
    for (int next : graph[cur])
    {
        if (!visited[next]){
            DFS(next);
        }
    }
}

int main(){
    // 1
    graph[1].push_back(2);
    graph[2].push_back(1);

    graph[1].push_back(4);
    graph[4].push_back(1);

    // 2
    graph[2].push_back(3);
    graph[3].push_back(2);

    // 4
    graph[4].push_back(5);
    graph[5].push_back(4);

    graph[4].push_back(6);
    graph[6].push_back(4);

    cout << "DFS走訪順序: ";
    DFS(1);
}

用Stack實作

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> graph[7];
bool visited[7];
void DFS(int start){
    stack<int> st;
    st.push(start);
    while (!st.empty()){
        int cur = st.top();
        st.pop();

        if (visited[cur])
            continue;
        visited[cur] = true;
        cout << cur << " ";
        for (int i=graph[cur].size()-1;i>=0;i--){
            int next = graph[cur][i];
            if (!visited[next]){
                st.push(next);
            }
        }
    }
}

int main(){
    graph[1].push_back(2);
    graph[2].push_back(1);

    graph[1].push_back(4);
    graph[4].push_back(1);

    graph[2].push_back(3);
    graph[3].push_back(2);

    graph[4].push_back(5);
    graph[5].push_back(4);

    graph[4].push_back(6);
    graph[6].push_back(4);

    cout << "DFS走訪順序: ";
    DFS(1);
}

DFS vs BFS比較

和BFS一樣，時間複雜度 O(V + E)

參考資料和書籍

1. https://zh.wikipedia.org/zh-tw/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2
2. https://www.youtube.com/watch?v=84jNzUOY78c