竞极 Ace

7 深度优先搜索

GESP C++ 六级：深度优先搜索（DFS）

核心目标：理解深度优先搜索的“一条路走到黑”思想，掌握递归与栈两种实现方式，熟练在树、图、网格上应用 DFS，掌握回溯、剪枝与记忆化技巧，能辨析 DFS 与 BFS 的适用场景。
DFS 就是“能往深处走就往深处走，走不通再回头”；递归是天然实现，栈是手动模拟；树/图/网格是三大应用场景；回溯是“选-递归-撤销”，剪枝是“提前判断不可行就返回”。

一、考纲定位

根据 CCF 官方考纲，GESP 六级明确要求掌握深度优先搜索（DFS） 和广度优先搜索（BFS） 的基本原理与实现，能够解决树、图、网格等结构上的搜索问题。

DFS 在六级考试中的考查分布：

考点 重要程度 典型考法
DFS 基本思想与递归实现 ★★★★★ 选择题、代码填空
树上的 DFS（遍历、深度、子树） 编程题、程序阅读
图上的 DFS（邻接表、连通分量） 编程题
网格上的 DFS（洪水填充、岛屿） 编程题高频
回溯法（全排列、组合、N 皇后） 编程题、代码填空
剪枝优化 ★★★★☆ 编程题
记忆化搜索
DFS 与 BFS 的区别 ★★★★★ 选择题高频

二、DFS 基本概念

2.1 什么是 DFS

深度优先搜索（Depth-First Search）是一种用于遍历或搜索树、图、网格等结构的算法。它的核心思想是：沿着一条路径尽可能深入地走，直到无法继续，然后回溯到上一个节点，尝试其他分支。

直观比喻：走迷宫时，你选择一条路一直走到底，如果遇到死胡同就退回到上一个岔路口，换一条路继续走，直到找到出口或遍历完所有可能。

2.2 DFS 的核心要素

要素 作用 示例
访问标记 防止重复访问 visited[] 数组
终止条件 何时停止深入 越界、已访问、达到目标
递归分支 下一步可以往哪走 上下左右、相邻节点
回溯 撤销当前选择，尝试其他分支 visited[x] = false

2.3 DFS 与 BFS 的区别

对比项 DFS BFS
数据结构 栈 / 递归 队列
遍历顺序 一条路走到黑 逐层扩展
最短路径 ❌ 不保证 ✅ 保证（无权图）
空间复杂度 O(深度) O(宽度)
适用场景 连通性、回溯、排列组合、树遍历 最短路径、层序、迷宫最短路

三、DFS 的两种实现方式

3.1 递归实现（最常用）

void dfs(当前状态) {
    if (终止条件) {
        处理结果;
        return;
    }
    标记当前状态已访问;
    for (所有可能的下一步) {
        if (下一步合法且未访问) {
            dfs(下一步);
        }
    }
    取消标记;   // 回溯时可能需要
}

3.2 栈实现（非递归）

void dfsStack(起点) {
    stack<状态> st;
    st.push(起点);
    visited[起点] = true;
    while (!st.empty()) {
        状态 cur = st.top(); st.pop();
        处理 cur;
        for (所有相邻状态) {
            if (!visited[相邻]) {
                visited[相邻] = true;
                st.push(相邻);
            }
        }
    }
}

注意：栈实现的 DFS 遍历顺序与递归不完全一致，但都能完成遍历。六级以递归实现为主。

四、树上的 DFS

4.1 树的存储

使用邻接表存储树（无向图，但无环）：

vector<int> adj[N];   // adj[u] 存储 u 的所有孩子/邻居

void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

4.2 树的前序遍历（DFS）

void dfs(int u, int parent) {
    cout << u << " ";              // 访问节点
    for (int v : adj[u]) {
        if (v != parent) {         // 避免回到父节点
            dfs(v, u);
        }
    }
}

关键：树是无环的，只需要避免回到父节点即可，不需要 visited 数组。

4.3 求树的深度

int depth(int u, int parent) {
    int maxDepth = 0;
    for (int v : adj[u]) {
        if (v != parent) {
            maxDepth = max(maxDepth, depth(v, u));
        }
    }
    return maxDepth + 1;
}

4.4 求子树大小

int subtreeSize(int u, int parent) {
    int size = 1;
    for (int v : adj[u]) {
        if (v != parent) {
            size += subtreeSize(v, u);
        }
    }
    return size;
}

4.5 求树的重心（了解）

树的重心是指删除该节点后，剩余各连通块大小的最大值最小的节点。可以通过 DFS 计算子树大小后判断。

五、图上的 DFS

5.1 图的存储

邻接表（最常用）：

vector<int> adj[N];   // adj[u] 存储 u 的所有邻居

void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);   // 无向图
}

5.2 图的 DFS 遍历

bool visited[N];

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";
    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

5.3 求连通分量个数

int countComponents(int n) {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);       // 一次 DFS 遍历一个连通分量
            cnt++;
        }
    }
    return cnt;
}

5.4 判断图是否有环

bool hasCycle(int u, int parent) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (!visited[v]) {
            if (hasCycle(v, u)) return true;
        } else if (v != parent) {
            return true;   // 遇到已访问且不是父节点，说明有环
        }
    }
    return false;
}

注意：无向图判环用 parent 避免误判；有向图判环需要用颜色标记（白/灰/黑）。

六、网格上的 DFS（洪水填充）

6.1 问题模型

给定一个二维网格，每个格子有不同状态（如陆地/水），求连通块数量、最大连通块面积等。

6.2 方向数组

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

6.3 岛屿数量（经典题）

问题：1 表示陆地，0 表示水，求岛屿数量（上下左右相连的陆地算一个岛）。

int n, m;
int grid[105][105];
bool visited[105][105];

void dfs(int x, int y) {
    visited[x][y] = true;
    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 &&
            !visited[nx][ny] && grid[nx][ny] == 1) {
            dfs(nx, ny);
        }
    }
}

int countIslands() {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j] && grid[i][j] == 1) {
                dfs(i, j);
                cnt++;
            }
        }
    }
    return cnt;
}

6.4 最大连通块面积

int dfs(int x, int y) {
    visited[x][y] = true;
    int area = 1;
    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 &&
            !visited[nx][ny] && grid[nx][ny] == 1) {
            area += dfs(nx, ny);
        }
    }
    return area;
}

6.5 迷宫可达性

bool canReach(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) return false;
    if (grid[x][y] == '#') return false;
    if (visited[x][y]) return false;
    if (x == ex && y == ey) return true;

    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        if (canReach(x + dx[i], y + dy[i])) return true;
    }
    return false;
}

七、回溯法（DFS 的重要应用）

7.1 回溯法模板

回溯法是 DFS 的一种应用，核心是“选择 → 递归 → 撤销选择”。

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        记录结果;
        return;
    }
    for (选择 : 选择列表) {
        做出选择;
        backtrack(路径, 新的选择列表);
        撤销选择;
    }
}

7.2 全排列

int n, a[10];
bool used[10];

void dfs(int step) {
    if (step == n) {
        for (int i = 0; i < n; i++) cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            a[step] = i;
            dfs(step + 1);
            used[i] = false;   // 回溯
        }
    }
}

7.3 组合数（从 n 个数中选 k 个）

int n, k, a[20];

void dfs(int step, int start) {
    if (step == k) {
        for (int i = 0; i < k; i++) cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = start; i <= n; i++) {
        a[step] = i;
        dfs(step + 1, i + 1);   // 下一层从 i+1 开始，避免重复
    }
}

7.4 N 皇后

int n, ans;
int col[20], diag1[40], diag2[40];

void dfs(int row) {
    if (row == n) {
        ans++;
        return;
    }
    for (int c = 0; c < n; c++) {
        if (!col[c] && !diag1[row + c] && !diag2[row - c + n]) {
            col[c] = diag1[row + c] = diag2[row - c + n] = 1;
            dfs(row + 1);
            col[c] = diag1[row + c] = diag2[row - c + n] = 0;
        }
    }
}

八、剪枝优化

8.1 什么是剪枝

剪枝是在 DFS 过程中，提前判断当前分支不可能产生有效解，直接返回，避免无效搜索。

8.2 常见剪枝类型

剪枝类型 说明 示例
可行性剪枝 当前状态已不满足约束 越界、已访问、和超过目标
最优性剪枝 当前代价已超过已知最优解 步数 ≥ 当前最优
顺序剪枝 调整搜索顺序，优先搜更可能的分支 先搜约束多的
记忆化剪枝 记录已搜索过的状态，避免重复 记忆化搜索

8.3 记忆化搜索

int dp[N];
bool vis[N];

int dfs(int u) {
    if (vis[u]) return dp[u];
    vis[u] = true;
    // 计算 dp[u]
    return dp[u];
}

九、GESP 六级 DFS 真题精讲

真题1：连通块计数（编程题）

给定一个 n×m 的网格，# 表示障碍，. 表示空地。求空地连通块的数量。

#include <iostream>
using namespace std;

int n, m;
char grid[105][105];
bool vis[105][105];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void dfs(int x, int y) {
    vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
            !vis[nx][ny] && grid[nx][ny] == '.') {
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    int cnt = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (!vis[i][j] && grid[i][j] == '.') {
                dfs(i, j);
                cnt++;
            }

    cout << cnt << endl;
    return 0;
}

真题2：树的重心（程序阅读）

给定一棵树，求删除哪个节点后，剩余最大连通块最小。

思路：DFS 计算每个节点的子树大小，然后对每个节点计算“删除后最大连通块”。

int n, sz[N], ans[N];

void dfs(int u, int parent) {
    sz[u] = 1;
    int maxPart = 0;
    for (int v : adj[u]) {
        if (v != parent) {
            dfs(v, u);
            sz[u] += sz[v];
            maxPart = max(maxPart, sz[v]);
        }
    }
    maxPart = max(maxPart, n - sz[u]);
    ans[u] = maxPart;
}

真题3：全排列（代码填空）

下面代码输出 1~n 的全排列，横线处应填入（ ）。

void dfs(int step) {
 if (step == n) {
     for (int i = 0; i < n; i++) cout << a[i] << " ";
     cout << endl;
     return;
 }
 for (int i = 1; i <= n; i++) {
     if (!used[i]) {
         used[i] = true;
         a[step] = i;
         dfs(step + 1);
         ______;
     }
 }
}

答案：used[i] = false;

真题4：DFS 与 BFS 区别（选择题）

以下关于 DFS 和 BFS 的说法，正确的是（ ）。
A. DFS 适合求无权图最短路径
B. BFS 适合求连通分量
C. DFS 用队列实现，BFS 用栈实现
D. DFS 不保证最短路径，BFS 保证无权图最短路径
答案：D

十、易错点汇总

  1. 忘记标记已访问：导致重复访问，甚至死循环。
  2. 回溯时忘记撤销标记：导致其他分支无法访问该节点。
  3. 网格 DFS 忘记边界检查：nx >= 0 && nx < n && ny >= 0 && ny < m 不能漏。
  4. 树 DFS 忘记传父节点：dfs(v, u) 避免回到父节点。
  5. 图 DFS 连通分量计数错误：外层循环遍历所有节点，未访问的才启动 DFS。
  6. 递归深度过大导致栈溢出：树退化为链时深度为 n，需注意数据范围。
  7. 回溯法组合问题起点写错：组合从 start 开始，排列用 used 数组。
  8. 剪枝条件写错：可行性剪枝和最优性剪枝要分清。
  9. 记忆化数组未初始化：vis[] 和 dp[] 要正确初始化。
  10. DFS 与 BFS 混淆：DFS 用栈/递归，BFS 用队列；DFS 不保证最短路。

十一、速查表

需求 写法 关键注意
DFS 递归模板 void dfs(状态) { if (终止) return; 标记; for (分支) dfs(新状态); 撤销; } 终止条件不能漏
DFS 栈模板 stack; push(起点); while (!empty) { pop; 处理; push 邻居; } 标记在入栈时
树 DFS dfs(u, parent) 用 parent 避免回头
图 DFS dfs(u) + visited[] 连通分量外层循环
网格 DFS dfs(x, y) + 方向数组 边界检查 + 已访问
全排列 used[i] 标记 + 回溯 撤销 used[i] = false
组合 dfs(step, start) 下一层从 i+1 开始
N 皇后 列、主对角线、副对角线标记 三个数组
剪枝 提前 return 可行性 + 最优性
记忆化 vis[] + dp[] 避免重复计算
连通分量 外层遍历 + 内层 DFS 未访问才启动

十二、总结

深度优先搜索是 GESP 六级搜索算法的核心内容。

  1. DFS 的核心是“一条路走到黑，走不通再回头”。
  2. 递归是 DFS 最自然的实现，栈是手动模拟。
  3. 树 DFS 用 parent 避免回头，图 DFS 用 visited 避免重复。
  4. 网格 DFS 用方向数组 + 边界检查，是洪水填充的基础。
  5. 回溯法 = 选择 → 递归 → 撤销选择，全排列、组合、N 皇后都是典型应用。
  6. 剪枝是提前判断不可行就返回，能大幅减少无效搜索。
  7. 记忆化搜索用 vis[] + dp[] 避免重复计算。
  8. DFS 不保证最短路径，BFS 保证无权图最短路径。
  9. 递归深度过大可能导致栈溢出，数据范围大时要改用栈或 BFS。
  10. 多练“连通块计数”“全排列”“树的重心”“N 皇后”四类题。

复习建议：先把网格 DFS 和树 DFS 的模板写熟，确保闭卷能默写；再重点练习回溯法（全排列、组合、N 皇后），理解“选择-递归-撤销”的流程；然后掌握连通分量计数和剪枝优化；最后用真题做限时训练。考试中先判断题目考的是树、图还是网格，再确定用哪种 DFS 模板，最后检查边界、标记和回溯。