深度优先搜索（DFS）

19 Oct 2024

1. 简介

深度优先搜索（Depth-First Search，DFS）是一种按“先走到底，再回退”的方式遍历状态的方法。每到一个位置，就先选择一条还没有尝试过的路继续向下搜索；当这条路走不通时，再回到上一步，尝试其他选择。

DFS 经常用递归实现。一次函数调用表示“已经走到当前状态”，函数内部枚举下一步所有可行的选择，并递归进入下一个状态。搜索结束后，程序会自动返回到上一层继续枚举，这个返回过程就是回溯。

它常见于排列、组合、迷宫和网格连通块等问题。不同题目的“下一步”不同，但基本结构相似：确定当前状态、判断结束条件、枚举可行选择，然后递归搜索。

2. 网格 DFS 的基本写法

在二维网格中，通常把一个格子的位置记为 (x, y)。如果只能上下左右移动，可以用两个数组表示四个方向：

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

从 (x, y) 走向相邻格子前，需要依次判断：

新坐标是否仍在网格范围内。
这个格子是否可以经过。
这个格子是否已经访问过。

访问过的格子要立刻标记。否则，搜索可能在相邻格子之间反复往返，导致无限递归。对于只需要判断或统计连通区域的题目，格子被标记后不必取消；因为以后不需要再次从这个格子开始搜索。

3. 例题：洛谷 P1451 细胞数量

题目给出一个由 0 和非 0 字符组成的网格。上下左右相邻的非 0 格子属于同一个细胞，要求统计细胞的数量。

可以从左到右、从上到下扫描整个网格。每当遇到一个尚未访问的非 0 格子，答案加一，并从它开始 DFS。该次 DFS 会把与它相连的所有格子都标记，因此同一个细胞不会被重复统计。

#include <bits/stdc++.h>
using namespace std;

const int N = 110;
int m, n;
char grid[N][N];
bool visited[N][N];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

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 >= m || ny < 0 || ny >= n) continue;
        if (grid[nx][ny] == '0') continue;
        if (visited[nx][ny]) continue;

        dfs(nx, ny);
    }
}

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

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

    cout << answer;
    return 0;
}

例如，网格中有三块彼此不相邻的非 0 区域时，外层循环会三次遇到新的未访问格子，因此答案是 3。每一个非 0 格子最多被 DFS 访问一次，时间复杂度为 O(mn)，其中 m 和 n 分别为网格的行数和列数。

DFS 的关键是先想清楚“一个状态是什么”和“下一步能走到哪里”。在网格题中，状态就是当前坐标；在排列题中，状态可以是已经填好的位置数量。只要把状态、终止条件和访问标记设计清楚，很多搜索问题都能自然地写成递归。

深度优先搜索（DFS）

Related Posts