深度优先搜索

引入

DFS 为图论中的概念，在 搜索算法 中，该词常常指利用递归函数方便地实现暴力枚举的算法，与图论中的 DFS 算法有一定相似之处，但并不完全相同。

解释

考虑这个例子：

例题

把正整数 $n$ 分解为 $3$ 个不同的正整数，如 $6=1+2+3$ ，排在后面的数必须大于等于前面的数，输出所有方案。

对于这个问题，如果不知道搜索，应该怎么办呢？

当然是三重循环，参考代码如下：

示例代码

for (int i = 1; i <= n; ++i)
  for (int j = i; j <= n; ++j)
    for (int k = j; k <= n; ++k)
      if (i + j + k == n) printf("%d = %d + %d + %d\n", n, i, j, k);

那如果是分解成四个整数呢？再加一重循环？

那分解成小于等于 $m$ 个整数呢？

这时候就需要用到递归搜索了。

该类搜索算法的特点在于，将要搜索的目标分成若干「层」，每层基于前几层的状态进行决策，直到达到目标状态。

考虑上述问题，即将正整数 $n$ 分解成小于等于 $m$ 个正整数之和，且排在后面的数必须大于等于前面的数，并输出所有方案。

设一组方案将正整数 $n$ 分解成 $k$ 个正整数 $a_1, a_2, \ldots, a_k$ 的和。

我们将问题分层，第 $i$ 层决定 $a_i$ 。则为了进行第 $i$ 层决策，我们需要记录三个状态变量： $n-\sum_{j=1}^i{a_j}$ ，表示后面所有正整数的和；以及 $a_{i-1}$ ，表示前一层的正整数，以确保正整数递增；以及 $i$ ，确保我们最多输出 $m$ 个正整数。

为了记录方案，我们用 arr 数组，第 i 项表示 $a_i$ . 注意到 arr 实际上是一个长度为 $i$ 的栈。

代码如下：

示例代码

int m, arr[103];  // arr 用于记录方案

void dfs(int n, int i, int a) {
  if (n == 0) {
    for (int j = 1; j <= i - 1; ++j) printf("%d ", arr[j]);
    printf("\n");
  }
  if (i <= m) {
    for (int j = a; j <= n; ++j) {
      arr[i] = j;
      dfs(n - j, i + 1, j);  // 请仔细思考该行含义。
    }
  }
}

// 主函数
scanf("%d%d", &n, &m);
dfs(n, 1, 1);

DFS 步骤

DFS 算法的基本步骤如下：

从起始节点开始，标记该节点为已访问。
对当前节点的所有未访问邻接节点，递归调用 DFS 算法。
当所有邻接节点都被访问完后，回溯到上一个节点。

DFS 通常借助递归实现，以下是伪代码：

DFS(node):
    标记 node 为已访问
    对 node 的每个邻接节点 neighbor:
        如果 neighbor 未被访问:
            DFS(neighbor)

经典例题及代码实现

题面描述

有一个由 0 和 1 组成的二维网格，1 代表陆地，0 代表水域。计算网格中岛屿的数量。岛屿是由水平或垂直相连的陆地形成的，且网格的四条边之外全是水域。

输入输出样例

输入：

这里第一行的 4 和 5 分别表示网格的行数和列数，接下来的四行描述了网格的具体内容。

输出：

表示网格中岛屿的数量为 3。

代码实现

示例代码

#include <iostream>
using namespace std;

const int MAXN = 1005;
int n, m;
int g[MAXN][MAXN];
bool vis[MAXN][MAXN];

// 深度优先搜索函数
void dfs(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) return;
    if (g[x][y] == 0 || vis[x][y]) return;
    vis[x][y] = true;
    dfs(x - 1, y);
    dfs(x + 1, y);
    dfs(x, y - 1);
    dfs(x, y + 1);
}

int main() {
    // 读入网格的行数和列数
    cin >> n >> m;
    // 读入网格的具体内容
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 1 && !vis[i][j]) {
                dfs(i, j);
                cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

总结

深度优先搜索（DFS）是信息学竞赛里一种强大且常用的算法，它能有效处理众多图和树相关的问题。其核心思想是递归地探索路径，直至无法继续，然后回溯。在使用 DFS 时，要注意标记已访问的节点，防止重复访问。通过不断练习和应用，能更好地掌握 DFS 算法，并运用它解决更复杂的问题。

例题

Status

Problem

深度优先搜索

On this page