# BFS 與 DFS

BFS 與 DFS 本質上是走訪一張圖的兩個演算法。事實上，我們也可以把一些問題轉化成圖論問題來走訪，而 BFS 與 DFS 有許多性質很適合來解決這些問題

<center>
<img src="https://miro.medium.com/v2/resize:fit:1280/1*GT9oSo0agIeIj6nTg3jFEA.gif" style="margin: 0 auto; display: block; width: 400px"></br>
圖源 : <a href="https://medium.com/analytics-vidhya/a-quick-explanation-of-dfs-bfs-depth-first-search-breadth-first-search-b9ef4caf952c">
Sebastian De Lima - A quick explanation of DFS & BFS </a>
</center>

## 廣度優先搜尋 Breadth-first Search

### 簡述
廣度優先搜尋簡稱 BFS，走訪順序如以下圖示:

<center>
<img src="https://upload.wikimedia.org/wikipedia/commons/1/1b/Breadth-first_tree.svg" style="margin: 0 auto; display: block; width: 400px">
</br>
<a href="https://zh.wikipedia.org/zh-tw/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2">圖源: 維基百科</a>
</center>

### 性質
1. 輸入一張圖 $G$ 與一個起點 $s$
2. 每到一個新的節點，就優先拜訪他的所有鄰居
3. 如果是連通圖，就會把所有點都走過一遍，邊則最多走過兩遍
4. 如果是連通圖，走訪每個點 $v$ 時所走的路徑，就是 $s$ 到 $v$ 的最短路徑
5. 如果圖不是連通圖，則會有連通塊 (connect conponent) 未被走訪

### C++ 實作

- 圖可以用鄰接串列 (adjacency list) 來儲存，比較方便
- 根據性質 2 ，發現符合「先進先出」性質，可用一個佇列 (queue) 來維護走訪清單
- 根據性質 3，為了避免拜訪重複的點，要用一個布林陣列來記錄節點是否拜訪過
- 根據性質 4，可以用一個陣列 $dis[~]$ 來記錄最短路徑
- 最短路徑的迭代方式: 未走訪鄰居 $v$ 一定會比現在走訪的點 $u$ 距離多 $1$
即 $dis[v]=dis[u]+1$

const int MAXN = 2e5 + 5;  // 點的數量
vector<int> g[MAXN];       // 鄰接串列儲存圖
bool vis[MAXN];            // 紀錄每個節點是否走訪過(在全域宣告會自動變成 false)
int dis[MAXN];             // 儲存從起點 s 到每個點的最短距離

void bfs(int s) {  // 起點
    queue<int> q;  // 這個存走訪名單
    q.push(s);     // s 第一個放入要走訪的名單

    while (!q.empty()) {
        int u = q.front();   // u 是現在走訪的節點
        q.pop();             // 把 u 從走訪名單上踢掉
        if(vis[u]) continue; // 走過就別再走
        vis[u] = true;       // 這樣子 u 就算是走訪過囉

        for (int v : g[u]) {          // 把 u 的每個鄰居 v 都放進名單中
            if (vis[v] == false) {    // 如果沒有走訪過這個鄰居
                q.push(v);            // 就把這個鄰居丟進去名單裡面
                dis[v] = dis[u] + 1;  // 順便算一下 s 到 v 的距離是多少
            }
        }
    }
}

其中，$dis[~]$ 並非執行 BFS 的必要條件，需要時在寫上去即可

### 時間複雜度
令節點數 $|V|=n$、邊數 $|E|=m$
- 每個節點都被拜訪過一次: $O(n)$
- 每條邊最多被走過兩次: $2m=O(m)$
- 總時間複雜度: $O(m+n)$

## 深度優先搜尋 Depth-first Search

### 簡述

深度優先搜尋簡稱 DFS，走訪順序如以下圖示:

<center>
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Depth-first-tree.svg/585px-Depth-first-tree.svg.png" style="margin: 0 auto; display: block; width: 400px">
</br>
<a href="https://zh.wikipedia.org/zh-tw/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2">
<p>圖源: 維基百科</p>
</a>
</center>

### 性質
1. 輸入僅有一張圖 $G$，沒有「起點」
2. 不管是否為連通圖，每個點都會被走訪過一遍，邊則最多走過兩遍
3. 可以利用「時間戳記」來判斷子節點
4. 每拜訪一個鄰居，就往該鄰居的鄰居拜訪
5. 走訪完的路徑會形成一棵 DFS 樹 (tree) 或是森林 (forest)

### C++ 實作
- 圖可以用鄰接串列 (adjacency list) 來儲存，比較方便
- 根據性質 1，必須用一個迴圈來跑過所有節點
- 根據性質 2，為了避免拜訪重複的點，要用一個布林陣列來記錄節點是否拜訪過
- 根據性質 4，符合「後進先出」性質，可以用一個 stack 來維護，亦可使用遞迴

#### stack 版本

const int MAXN = 2e5 + 5;  // 點的數量
vector<int> g[MAXN];       // 鄰接串列儲存圖
bool vis[MAXN];            // 紀錄每個節點是否走訪過(在全域宣告會自動變成 false)

void run_dfs(int s) {  // 起點
    stack<int> stk;    // 這個存走訪名單
    stk.push(s);       // s 第一個放入要走訪的名單
    while (!stk.empty()) {
        int u = stk.top();  // u 是現在走訪的節點
        stk.pop();          // 把 u 從走訪名單上踢掉
        vis[u] = true;      // 這樣子 u 就算是走訪過囉

        for (int v : g[u]) {      // 把 u 的每個鄰居 v 都放進名單中
            if (vis[v] == false)  // 如果沒有走訪過這個鄰居
                stk.push(v);      // 就把這個鄰居丟進去名單裡面
        }
    }
}
void dfs(int n) {                   // 塞入節點個數
    for (int i = 1; i <= n; i++) {  // 窮舉所有節點
        if (vis[i] == false)        // 如果該鄰居沒拜訪過
            run_dfs(i);             // 就去他家逛逛吧
    }
}

#### 遞迴版本

const int MAXN = 2e5 + 5;  // 點的數量
vector<int> g[MAXN];       // 鄰接串列儲存圖
bool vis[MAXN];            // 紀錄每個節點是否走訪過(在全域宣告會自動變成 false)

void run_dfs(int u) {
    vis[u] = true;  // 這樣就算是走過囉
    for (int v : g[u]) {
        if (vis[v] == false)  // 如果該鄰居沒拜訪過
            run_dfs(v);       // 就去他家逛逛吧
    }
}
void dfs(int n) {                   // 塞入節點個數
    for (int i = 1; i <= n; i++) {  // 窮舉所有節點
        if (vis[i] == false)        // 如果該鄰居沒拜訪過
            run_dfs(i);             // 就去他家逛逛吧
    }
}

### 時間戳記
我們可以在上述遞迴版本的程式碼中加入:
- $d[i]$ : 發現節點 $i$ 的時間 (discovery time)
- $f[i]$ : 節點 $i$ 完成所有鄰居拜訪的時間 (finishing time)

// DFS 遞迴版本程式片段
void run_dfs(int u) {
    vis[u] = true;
    d[u] = ++timestamp;  // 紀錄發現時間
    for (int v : g[u]) {
        if (vis[v] == false)
            run_dfs(v);
    }
    f[u] = ++timestamp;  // 紀錄結束時間
}

會發現時間戳記有以下性質:
1. 對於所有節點 $v$，每個 $d[v]$ 與 $f[v]$ 都有獨一無二的數字
2. 對於所有節點 $v$，$1\leq d[v]<f[v]\leq 2n$

### 括號定理

當我們把所有節點 $v$ 的發現與結束時間化在數線上，會形成好幾個區間

<center>
<img src="https://hackmd.io/_uploads/B1cGUux-Je.png" style="margin: 0 auto; display: block; width: 600px">
圖源 : CLRS 演算法課本
</center>

</br>

以上圖為例，左邊是原本的圖；右邊則是把時間戳記畫在數線上

藉由上圖，會發現以下性質:
對於任兩節點 $u$ 與 $v$ 在 DFS 森林中
1. 如果區間 $[d[u], f[u]]$ 與 $[d[v], f[v]]$ 沒有交集，則 $u$ 與 $v$ 沒有血緣關係
2. 如果區間 $[d[u], f[u]]$ 包含 $[d[v], f[v]]$，則 $u$ 為 $v$ 的祖先
3. 如果區間 $[d[v], f[v]]$ 包含 $[d[u], f[u]]$，則 $u$ 為 $v$ 的後代

可以得到推論: 在一個 DFS 森林中，$d[u]<d[v]<f[v]<f[u]$ 若且唯若，$v$ 是 $u$ 的後代

### 白路徑定理
在一張圖 $G$ 的 DFS 森林中，在時間處於 $d[u]$ 時，有一條從 $u$ 到 $v$ 的路徑是完全由白點組成若且為若 $v$ 是 $u$ 的後代

這些定理與性質會在樹的演算法、[Kosaraju 演算法](https://hackmd.io/@ShanC/Kosaraju)、[拓樸排序 (Topological Sort)](https://hackmd.io/@ShanC/topological_sort) 中有更多討論與應用

### 時間複雜度
令節點數 $|V|=n$、邊數 $|E|=m$
- 每個節點都被拜訪過一次: $O(n)$
- 每條邊最多被走過兩次: $2m=O(m)$
- 總時間複雜度: $O(m+n)$

## 例題說明: [迷宮問題](https://zerojudge.tw/ShowProblem?problemid=a982)

### 題目
給一個 $N\times N$ 的迷宮，求從 $(2, 2)$ 到 $(n - 1, n - 1)$ 的最短路徑

### 題解
這題顯然是要先將網格圖轉化成圖論的圖，其實把每個點 (point) 視為節點 (vertex) 就很好去想要怎麼找最短路徑。找最短路徑可以使用 BFS，因為他走訪的點都會是相對於起點的最短路徑。

### 程式碼

#include <bits/stdc++.h> // 萬用標頭檔
using namespace std;

const int N = 105;

struct Point {
    int x, y;
};
int n, dis[N][N];
int dir[4][2] = {
    {1,  0 },
    {0,  1 },
    {-1, 0 },
    {0,  -1}
};

int main() {
    cin >> n;
    char c;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> c;
            if (c == '#')
                dis[i][j] = -1;
            else
                dis[i][j] = 0;
        }
    }

    queue<Point> q;
    q.push({1, 1});
    dis[1][1] = 1;
    while (!q.empty()) {
        Point u = q.front();
        q.pop();
        if (u.x == n - 2 && u.y == n - 2)
            break;  // 找到終點就結束迴圈

        for (int i = 0; i < 4; i++) {
            Point v = {u.x + dir[i][0], u.y + dir[i][1]};
            if (dis[v.x][v.y] == 0) {
                q.push({v.x, v.y});
                dis[v.x][v.y] = dis[u.x][u.y] + 1;
            }
        }
    }

    if (dis[n - 2][n - 2])
        cout << dis[n - 2][n - 2] << '\n';
    else
        cout << "No solution!\n";

    return 0;
}

## 例題說明: [排列](https://zerojudge.tw/ShowProblem?problemid=i646)

### 題目
把英文小寫字母前 $n$ 項的所有排列方法列出來，其中 $n \leq 7$

### 題解

以 $n=3$ 為例，可以用樹狀圖找出以下可能

<center>
<img src="https://hackmd.io/_uploads/Bk1S4qeWye.png" style="margin: 0 auto; display: block; width: 600px">
</center>

把問題轉化為樹狀圖之後，就可以用 DFS 走訪每個葉結點

### 程式碼

#include <bits/stdc++.h>
using namespace std;

int n;
map<char, bool> mp;

void dfs(string str) {
    if (str.length() == n) {
        cout << str << '\n';
        return;
    }
    for (int i = 0; i < n; i++) {
        char c = i + 'a';
        if (mp[c] == 0) {
            mp[c] = true;
            dfs(str + c);
            mp[c] = false;
        }
    }
}
int main() {
    while (cin >> n && n)
        dfs("");
    return 0;
}

## 小結
### BFS
- 優點:
適合找出最短路徑
如果是要求出其中一條路徑，BFS 較穩定且有效率
- 缺點:
耗費太多記憶體 (其實也還好

### DFS
- 優點:
適合窮舉所有可能
有時間戳記的性質，在走訪樹的時候比較好去做擴充
- 缺點:
如果要找出最短路徑比較沒效率，因為必須跑完整張圖

**遇到題目時要先分析到底哪個方法更適合**

## 題目練習

[Zerojudge a982. 迷宮問題#1](https://zerojudge.tw/ShowProblem?problemid=a982)
[CSES Subordinates](https://cses.fi/problemset/task/1674/)
[Zerojudge a290. 新手訓練系列 ~ 圖論](https://zerojudge.tw/ShowProblem?problemid=a290)
[CSES Counting Rooms](https://cses.fi/problemset/task/1192)
[Zerojudge l747. 連線](https://zerojudge.tw/ShowProblem?problemid=l747)
[Zerojudge j124. APCS 3. 石窟探險](https://zerojudge.tw/ShowProblem?problemid=j124)
[Zerojudge b967. APCS 4. 血緣關係](https://zerojudge.tw/ShowProblem?problemid=b967)
[Zerojudge i646. 排列組合-排列](https://zerojudge.tw/ShowProblem?problemid=i646)
[CSES Tree Matching](https://cses.fi/problemset/task/1130/) (跟樹的葉子有關)
[Zerojudge c291. APCS 2017-0304-2小群體](https://zerojudge.tw/ShowProblem?problemid=c291)
[CSES Message Route](https://cses.fi/problemset/task/1667/)
[Zerojudge n751. 00941 - Permutations](https://zerojudge.tw/ShowProblem?problemid=n751)
[Zerojudge a469. 10063 - Knuth's Permutation](https://zerojudge.tw/ShowProblem?problemid=a469)

----

## 參考資料
- Introduction to Algorithms, Fourth Edition
- [geeksforgeeks](https://www.geeksforgeeks.org/iterative-depth-first-traversal/)
- [DFS與BFS by Darth-Phoenix](https://hackmd.io/@rd2865OAQZSLjri24DYcow/B1zalLE6u)
- [維基百科](https://zh.wikipedia.org/zh-tw/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2024/10/31