簡介#
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);
這樣的演算法用途非常多，也是其他許多複雜的圖論演算法的基礎。
注意
請注意，vis[u] = true 一定要放在 dfs(u) 的前面，不然還是可能會因為一直來回走訪兩個節點進入無限遞迴。
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);
}
}
雖然從上面的例子可能看不出這個技巧太大的優勢，但是在一些複雜的題目中，這個技巧可以讓你的程式碼更簡潔，也更容避免錯誤。類似蓋邊界的概念其實在很多題目中也會以不同的方式出現，在未來的學習中我們會再介紹。
