DFS 深度優先搜尋｜完整教學

先備知識

基本資料結構：堆疊（stack）、遞迴呼叫堆疊、陣列 / 鏈結串列
圖論基礎：節點（vertex）、邊（edge），有向 / 無向圖、加權 / 無權圖
複雜度記號：O(V+E)、最壞 / 平均情況概念

小提醒：若題目是「網格」(grid)（例如 0/1 地圖），也可以把每個格子視作節點、上下左右為邊。

什麼是 DFS？

DFS（Depth-First Search，深度優先）是沿著一條路徑一路走到不能再走才回頭（backtrack）的圖搜尋策略。它天然對應「遞迴」或用「顯式堆疊」實作。

應用：連通塊數量、拓樸排序、有向環檢測、樹的前中後序、回溯（N 皇后 / 全排列）、網格島嶼數…
特性：記憶體小、實作簡潔；但遞迴太深可能觸發堆疊上限（需改疊代或增加限制）。

通用模板（遞迴 / 疊代）

遞迴模板

// 假設使用鄰接串列 adj，visited[] 紀錄是否走過
void dfs(u){
    visited[u] = true;
    // 這裡可處理節點 u（進點時機）
    for (auto v : adj[u]){
        if (!visited[v]) dfs(v);
    }
    // 這裡可處理節點 u（離點時機，用於拓樸排序等）
}

「進點 / 離點」兩個時機非常關鍵：例如拓樸排序在「離點」時把節點推入序列。

疊代（顯式 stack）模板

# 使用手動 stack 取代遞迴，避免爆棧
stack<int> st;
st.push(s);
while(!st.empty()){
    int u = st.top(); st.pop();
    if (visited[u]) continue;
    visited[u] = true;
    // 處理 u
    for (int v : adj[u]){
        if (!visited[v]) st.push(v);
    }
}

圖的表示法（競賽常用）

1) 向量鄰接串列（簡潔易讀）

// C++（現代）：vector<int> adj[N];
for (int i=0;i<m;i++){
    int a,b; // 讀邊
    adj[a].push_back(b);
    adj[b].push_back(a); // 無向圖
}

2) 靜態前向星（C++98 友善、免動態配置）

// 陣列版本：head[u] 為 u 的第一條邊索引，next[i] 為同起點的下一條
const int MAXE = 4000005; // 2*m 上限
int head[MAXN], to[MAXE], nxt[MAXE], ecnt=0;
void addEdge(int u,int v){
  to[++ecnt]=v; nxt[ecnt]=head[u]; head[u]=ecnt;
}

四個經典範例與程式

範例 A：無向圖遍歷與連通塊數（朋友群組數）

題意：給 n 個人與 m 條友情（無向邊），求共有幾個獨立朋友群組（連通塊）。

#include <cstdio>
const int MAXN=200000, MAXE=400000;
int n,m,head[MAXN+5],to[MAXE+5],nxt[MAXE+5],ecnt=0,vis[MAXN+5];
void addEdge(int u,int v){ to[++ecnt]=v; nxt[ecnt]=head[u]; head[u]=ecnt; }
void dfs(int u){
  vis[u]=1;
  for(int e=head[u]; e; e=nxt[e]){
    int v=to[e];
    if(!vis[v]) dfs(v);
  }
}
int main(){
  std::scanf("%d%d",&n,&m);
  for(int i=1;i<=m;i++){ int a,b; std::scanf("%d%d",&a,&b); addEdge(a,b); addEdge(b,a); }
  int cc=0;
  for(int i=1;i<=n;i++) if(!vis[i]){ dfs(i); cc++; }
  std::printf("%d\n",cc);
  return 0;
}

Python（簡潔版）

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,sys.stdin.readline().split())
adj=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,sys.stdin.readline().split())
    adj[a].append(b); adj[b].append(a)
vis=[False]*(n+1)
def dfs(u):
    vis[u]=True
    for v in adj[u]:
        if not vis[v]: dfs(v)
cc=0
for i in range(1,n+1):
    if not vis[i]:
        dfs(i); cc+=1
print(cc)

範例 B：有向圖環檢測（DFS 著色法）

題意：給有向圖，檢查是否存在環（回邊）。

做法：著色 0=未訪、1=在遞迴堆疊、2=已完成；若從 1 再遇到 1，則有環。

// C++
#include <bits/stdc++.h>
using namespace std;
const int N=200000;
vector<int> g[N+1];
int n,m,color[N+1];
bool hasCycle=false;
void dfs(int u){
  color[u]=1;
  for(int v: g[u]){
    if(color[v]==0) dfs(v);
    else if(color[v]==1) hasCycle=true; // 回邊
  }
  color[u]=2;
}
int main(){
  ios::sync_with_stdio(false); cin.tie(nullptr);
  cin>>n>>m;
  for(int i=0;i<m;i++){ int a,b; cin>>a>>b; g[a].push_back(b); }
  for(int i=1;i<=n;i++) if(color[i]==0) dfs(i);
  cout << (hasCycle? "YES":"NO") << "\n";
  return 0;
}

範例 C：網格島嶼數（4-方向 DFS）

題意：給 0/1 矩陣，1 表陸地，數出島嶼個數。

// C++
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<string> a;
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
void dfs(int x,int y){
  a[x][y]='0';
  for(int k=0;k<4;k++){
    int nx=x+dx[k], ny=y+dy[k];
    if(0<=nx && nx<n && 0<=ny && ny<m && a[nx][ny]=='1') dfs(nx,ny);
  }
}
int main(){
  ios::sync_with_stdio(false); cin.tie(nullptr);
  cin>>n>>m; a.resize(n);
  for(int i=0;i<n;i++) cin>>a[i];
  int cnt=0;
  for(int i=0;i<n;i++) for(int j=0;j<m;j++)
    if(a[i][j]=='1'){ dfs(i,j); cnt++; }
  cout<<cnt<<"\n";
  return 0;
}

範例 D：回溯（全排列）—— DFS 作為解空間搜尋

// C#（配合你課程需求）
using System;
class P {
  static int n;
  static bool[] used = new bool[15];
  static int[] buf = new int[15];
  static void D(int depth){
    if(depth==n){
      for(int i=0;i<n;i++){ if(i>0) Console.Write(" "); Console.Write(buf[i]); }
      Console.WriteLine(); return;
    }
    for(int x=1;x<=n;x++){
      if(used[x]) continue;
      used[x]=true; buf[depth]=x;
      D(depth+1);
      used[x]=false;
    }
  }
  static void Main(){
    n=int.Parse(Console.ReadLine());
    D(0);
  }
}

回溯 = DFS +「選 / 不選 + 邊界條件 + 撤銷」。常見題型：子集合枚舉、排列、N 皇后、數獨。

常見陷阱與最佳實務

忘記 visited：無向圖若不標記，會在兩端之間來回遞迴。
遞迴過深：C++/Python 可能爆棧；可改顯式 stack或提高遞迴限制。
圖不連通：主程式需從每個未訪節點再次呼叫 DFS。
網格越界：條件判斷順序要先保證索引安全。
方向性：有向圖與無向圖在建邊時不同，別誤加雙向。

時間與空間複雜度

時間：每條邊、每個點至多被處理一次，O(V+E)。
空間：visited 與遞迴堆疊（最深可能達 O(V)）。

解題檢查清單（交作業前對照）

是否正確建圖？（有向 / 無向、邊數是否翻倍）
是否對所有未訪起點呼叫 DFS？
是否正確維護 visited / 顏色？
是否在正確時機（進點 / 離點）處理答案？
是否考慮極端情況：n=1、孤立點、空圖、長鏈？

DFS 深度優先搜尋：完整教學

遞迴模板

疊代（顯式 stack）模板

1) 向量鄰接串列（簡潔易讀）

2) 靜態前向星（C++98 友善、免動態配置）

範例 A：無向圖遍歷與連通塊數（朋友群組數）

Python（簡潔版）

範例 B：有向圖環檢測（DFS 著色法）

範例 C：網格島嶼數（4-方向 DFS）

範例 D：回溯（全排列）—— DFS 作為解空間搜尋