深度优先搜索（DFS）

深度优先搜索会沿着一条可行分支尽量向深处访问，走不通时再返回到最近的分叉点。递归调用的进入与返回，正好对应搜索树中的深入与回退；DFS 既可遍历显式图，也可搜索由状态和转移构成的隐式图。

1. 图上的基本框架

图可能含环，因此要用访问数组避免重复访问。以下模板从 s 出发，访问它所在的全部连通部分；若要统计全图连通块，再枚举所有未访问的起点调用它。

vector<vector<int>> g;
vector<bool> vis;

void dfs(int u) {
    vis[u] = true;
    // 处理结点 u
    for (int v : g[u]) {
        if (!vis[v]) dfs(v);
    }
}

int components = 0;
for (int i = 1; i <= n; ++i) {
    if (!vis[i]) {
        ++components;
        dfs(i);
    }
}

对于以无向边给出的树，也可以传入 fa 来跳过父结点；这样常用于计算深度、子树大小和树形 DP。

2. 递归与显式栈

递归实现最直观，但深度很大时可能造成调用栈过深。显式栈能避免这一问题。若希望迭代版本的访问顺序接近递归版本，通常将邻接点按相反顺序压栈。

void dfsIter(int s) {
    stack<int> st;
    st.push(s);
    vis[s] = true;
    while (!st.empty()) {
        int u = st.top(); st.pop();
        // 处理结点 u
        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = true;
                st.push(v);
            }
        }
    }
}

3. 常见应用

连通块与 Flood Fill：把网格中的每个格子看作结点，只向合法的上下左右邻格递归，即可统计岛屿、填充颜色或求区域大小。路径搜索：递归参数可携带当前位置、剩余步数或当前答案；到达目标后记录结果。子树信息：先递归孩子、后合并答案，可得到子树大小、最大深度等后序信息。

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void floodFill(int x, int y) {
    vis[x][y] = true;
    for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (inside(nx, ny) && !vis[nx][ny] && grid[nx][ny] == '#')
            floodFill(nx, ny);
    }
}

4. 复杂度与使用边界

邻接表中，每个点和每条边至多被检查常数次，时间复杂度为 O(V + E)，访问数组和递归栈额外占 O(V) 空间。邻接矩阵需要扫描整行，时间为 O(V²)。

图遍历的 vis 通常一旦标记便不撤销；而枚举方案时的“路径内已用”状态往往需要撤销，那是回溯搜索的做法。遇到无权最短路时，优先使用 BFS，而不是 DFS。