DFS

簡介

DFS (Depth First Search) 深度優先搜尋演算法，是一種在圖論中非常基礎且重要的技巧，主要是用來走訪整張圖。

基本概念就是，透過遞迴一直盡可能深的搜尋下去，直到沒有路了在退回來之前的岔路繼續搜尋其他沒走過的路。

實作

如果你熟悉遞迴的話，應該很容易想到下面這樣的程式碼：

void dfs(int v) {
    // 對所有 v 走得到的點繼續 dfs
    for (auto u : g[v]) {
        dfs(u);
    }
}

其實就跟 遞迴枚舉 的程式碼寫起來很像，遞迴枚舉是在走訪遞迴樹，這邊是在走訪一張圖！

但是上面的程式碼其實還有一個非常大的問題，這會導致整個程式進入無限的遞迴，因為你會對走過的節點一直重複的走！

為了解決這個問題，我們需要再開一個 vis[] 布林陣列來記錄哪些點已經被走過了，如果走過就直接忽略，不需要直接 DFS 進去：

bool vis[MAXN]; // 最多 MAXN 個節點

void dfs(int v) {
    for (auto u : g[v]) {
        // 如果走過就忽略
        if (vis[u]) continue;
        // 把節點標記成走過
        vis[u] = true;
        dfs(u);
    }
}

// 從點 1 開始 DFS
vis[1] = true;
dfs(1);

這樣的演算法用途非常多，也是其他許多複雜的圖論演算法的基礎。

void dfs(int v) {
    for (auto u : g[v]) {
        if (vis[u]) continue;
        dfs(u);
        vis[u] = true;
    }
}

DFS 時紀錄訊息

在更困難的題目，DFS 常常不只是做 DFS 而已，其中一個例子就是在「DFS 中紀錄訊息」。

比如說你今天想知道每個節點與起點的距離，這時候你可以在 DFS 的時候多加一個參數 d 並紀錄進 dist 陣列：

int dist[MAXN];

void dfs(int v, int d) {
    dist[v] = d;
    // 紀錄起點到目前節點 v 的距離為 d
    for (auto u : g[v]) {
        if (vis[u]) continue;
        // 這邊記得要 +1
        dfs(u, d + 1);
        vis[u] = true;
    }
}

二維平面上的 DFS

圖論有一種類型的題目就是在二維平面上操作（比如走迷宮等等），或許熟習實作的你已經知道該怎麼做了，不過這邊還是有一些值得一提的小技巧可以介紹！

第一個技巧就是用一個陣列來記錄四個方向的移動，這樣就可以很方便的實作 DFS 而不需要寫很多的程式碼：

// 對於每個方向的移動
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void dfs(int x, int y) {
    // 枚舉四個方向
    for (int i = 0; i < 4; i++) {
        // 移動到新的座標
        int nx = x + dx[i];
        int ny = y + dy[i];
        // 超出邊界或是已經走過就忽略
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (vis[nx][ny]) continue;
        // 標記成走過
        vis[nx][ny] = true;
        // 繼續 DFS
        dfs(nx, ny);
    }
}

另外還有一個技巧就是「蓋邊界」，預先把邊界標記進 vis[] 陣列，這樣就不用在 DFS 的時候一直檢查是否超出邊界：

// 蓋邊界
for (int i = 0; i < n; i++) {
    vis[i][0] = vis[i][m - 1] = true;
}
for (int i = 0; i < m; i++) {
    vis[0][i] = vis[n - 1][i] = true;
}

// DFS
void dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (vis[nx][ny]) continue;
        vis[nx][ny] = true;
        dfs(nx, ny);
    }
}

雖然從上面的例子可能看不出這個技巧太大的優勢，但是在一些複雜的題目中，這個技巧可以讓你的程式碼更簡潔，也更容避免錯誤。類似蓋邊界的概念其實在很多題目中也會以不同的方式出現，在未來的學習中我們會再介紹。