DFS 基础

概念讲解

什么是 DFS？

DFS（深度优先搜索）是一种沿着一条路径尽可能深地搜索的算法。

DFS 特点

  • 使用栈或递归实现
  • 空间复杂度 O(h)，h 是深度
  • 不保证找到最短路径

DFS 框架

void dfs(状态) {
    if (到达终点) {
        处理结果;
        return;
    }
    
    for (枚举所有可能) {
        if (合法) {
            标记已访问;
            dfs(新状态);
            恢复现场;  // 回溯
        }
    }
}

经典应用

1. 连通块计数

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

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

2. 全排列

123456789101112131415161718int path[10];
bool used[10];

void dfs(int depth, int n) {
    if (depth == n) {
        for (int i = 0; i < n; i++) cout << path[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            path[depth] = i;
            used[i] = true;
            dfs(depth + 1, n);
            used[i] = false;
        }
    }
}

考点分析

初赛考查方式

  1. 程序阅读： DFS 执行过程
  2. 编程题： DFS 应用

常见考点

  • DFS 执行顺序
  • 回溯法
  • 连通块计数

例题精讲

例题 1：连通块

题目： 求网格中连通块的数量。

解答：

遍历每个格子，未访问则 DFS，计数加一。

练习题

  1. DFS 和 BFS 的区别是什么？
查看答案
特性 DFS BFS
数据结构 栈/递归 队列
搜索方式 深度优先 广度优先
最短路径 不保证 保证（无权图）
空间复杂度 O(h) O(w)

h 是深度，w 是宽度。

  1. 回溯法的关键是什么？
查看答案

回溯法的关键是恢复现场：

  1. 做选择（标记已访问）
  2. 递归搜索
  3. 撤销选择（恢复状态）
123used[i] = true;   // 做选择
dfs(depth + 1);   // 递归
used[i] = false;  // 恢复现场
  1. 如何用 DFS 求全排列？
查看答案

使用回溯法，维护路径数组和访问标记：

123456789101112131415161718int path[10];
bool used[10];

void dfs(int depth, int n) {
    if (depth == n) {
        // 输出当前排列
        for (int i = 0; i < n; i++) cout << path[i] << " ";
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            path[depth] = i;
            used[i] = true;
            dfs(depth + 1, n);
            used[i] = false;  // 回溯
        }
    }
}

易错点

⚠️ 注意：

  1. DFS 不保证最短路径
  2. 回溯要恢复现场
  3. 注意边界条件
  4. 递归要有终止条件