第18篇-DFS深度优先搜索-从二维网格到路径搜索

概述

学完回溯之后，我们继续看另一个非常重要的搜索思想：DFS，深度优先搜索。

很多初学者会把 DFS 和回溯混在一起。
它们确实很像，因为回溯本身就常常是 DFS 的一种应用。
但 DFS 的关注点更广，通常是：

沿着一条路尽可能往深处走，走不通再回退，换另一条路

DFS 最常见的使用场景包括：

• 二维网格搜索
• 连通块统计
• 岛屿问题
• 路径是否存在
• 树的遍历
• 图的遍历

这类题的共同点是：需要从一个起点出发，把能到达的地方全部走一遍。

如果你已经学过递归和回溯，那么 DFS 会非常自然。
它通常可以直接用递归写，也可以用显式栈写。

这篇文章会围绕 DFS 的基础形态展开：

学完这篇，你应该能把 DFS 视为一种标准搜索手段，并能写出网格遍历、连通块统计和路径搜索的基础代码。

核心概念：DFS 到底是什么

DFS 的全称是 Depth First Search，中文叫深度优先搜索。

它的核心思想是：

先沿着一条路径一直走到尽头，再回头尝试其他路径

这和广度优先搜索 BFS 正好相对。
BFS 是一层一层扩展，DFS 是一条路走到底。

DFS 的典型过程

假设从点 A 出发，周围可以走到 B、C、D：

A -> B -> E -> F
-> C -> …
-> D -> …

DFS 会优先沿着 A -> B -> E -> F 这条路走深。
走不下去之后，再回到 A，尝试 C、D。

DFS 和递归的关系

DFS 很适合递归写，因为递归本身就天然适合“先深入，再返回”的过程。

一个最基础的 DFS 结构是：

void dfs(当前节点) {
if (终止条件) {
return;
}

标记当前节点;

for (下一个节点 : 所有可行邻居) {
dfs(下一个节点);
}
}

这个结构和回溯非常接近。
区别在于，DFS 更强调“遍历图或网格”，回溯更强调“枚举方案并恢复现场”。

DFS 就是沿着一条路径尽可能向深处搜索，直到不能继续再回退。

DFS 基本模板：先记住这几行

DFS 题目看起来很多，但基础模板通常是固定的。

网格 DFS 模板

void dfs(int x, int y) {
if (越界 || 已访问 || 不满足条件) {
return;
}

标记访问;

for (四个方向) {
dfs(nx, ny);
}
}

图 DFS 模板

void dfs(int node) {
if (已访问) {
return;
}

标记访问;

for (int next : graph[node]) {
dfs(next);
}
}

树 DFS 模板

void dfs(TreeNode root) {
if (root == null) {
return;
}

dfs(root.left);
dfs(root.right);
}

DFS 的核心不是代码形式，而是思路：

• 从当前点出发
• 判断是否可以继续
• 标记当前状态
• 递归访问下一个位置

DFS 的代码一般都长得很像，关键是判断条件、访问标记和下一步搜索方向。

例题一：二维网格中的 DFS 遍历

二维网格题是 DFS 的经典入门场景。

题目可以抽象成：

给定一个二维网格，从某个起点出发，访问所有满足条件的格子。

例如，网格中有 0 和 1：

1 1 0 0
1 0 0 1
0 0 1 1

如果我们要从某个 1 出发，把相连的 1 都找到，就需要 DFS。

四个方向的定义

二维网格通常有四个方向：

上、下、左、右

可以用两个数组表示方向偏移：

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

这样就能统一枚举四个邻居。

Java 代码实现

class Solution {
private int m;
private int n;
private int[] dx = {–1, 1, 0, 0};
private int[] dy = {0, 0, –1, 1};

public void dfs(char[][] grid, int x, int y, boolean[][] visited) {
if (x < 0 || x >= m || y < 0 || y >= n) {
return;
}
if (visited[x][y] || grid[x][y] == '0') {
return;
}

visited[x][y] = true;

for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
dfs(grid, nx, ny, visited);
}
}
}

为什么要先判断越界和访问状态

网格搜索里最常见的错误就是越界。

如果没有先判断：

if (x < 0 || x >= m || y < 0 || y >= n)

那么后续访问 grid[x][y] 时就会报错。

如果不判断 visited[x][y]，DFS 可能会在相邻格子之间来回走，形成死循环。

所以判断顺序通常是：

二维网格 DFS 的关键是方向枚举、越界判断和访问标记。

例题二：岛屿数量

题目：

给定一个由 1 和 0 组成的二维网格，1 表示陆地，0 表示海水，求岛屿的数量。

岛屿定义为上下左右相连的陆地块。

解题思路

这道题本质上是：
统计网格中有多少个连通块。

做法是：

这样每个岛屿只会统计一次。

Java 代码实现

class Solution {
private int m;
private int n;
private int[] dx = {–1, 1, 0, 0};
private int[] dy = {0, 0, –1, 1};

public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}

m = grid.length;
n = grid[0].length;
boolean[][] visited = new boolean[m][n];
int count = 0;

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

return count;
}

private void dfs(char[][] grid, int x, int y, boolean[][] visited) {
if (x < 0 || x >= m || y < 0 || y >= n) {
return;
}
if (visited[x][y] || grid[x][y] == '0') {
return;
}

visited[x][y] = true;

for (int k = 0; k < 4; k++) {
dfs(grid, x + dx[k], y + dy[k], visited);
}
}
}

为什么 DFS 后岛屿只会统计一次

假设一个岛屿里有多个相连的 1：

1 1
1 0

当我们从左上角开始 DFS 时，会把整个连通块里的所有 1 都标记为已访问。
之后再遍历到同一个岛屿的其他格子时，它们已经被访问过，所以不会重复计数。

复杂度分析

• 时间复杂度：O(m * n)，每个格子最多访问一次
• 空间复杂度：O(m * n)，visited 数组和递归栈

遇到一个新的陆地就开始 DFS，把整个连通块淹没掉，然后岛屿数加一。

例题三：岛屿面积

题目：

计算最大岛屿的面积，即连通陆地格子的最大数量。

解题思路

这和岛屿数量很像，只不过不是统计岛屿个数，而是统计当前连通块的大小。

DFS 的返回值可以表示：

从当前位置出发，当前连通块的面积

Java 代码实现

class Solution {
private int m;
private int n;
private int[] dx = {–1, 1, 0, 0};
private int[] dy = {0, 0, –1, 1};

public int maxAreaOfIsland(int[][] grid) {
m = grid.length;
n = grid[0].length;
boolean[][] visited = new boolean[m][n];
int maxArea = 0;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && grid[i][j] == 1) {
maxArea = Math.max(maxArea, dfs(grid, i, j, visited));
}
}
}

return maxArea;
}

private int dfs(int[][] grid, int x, int y, boolean[][] visited) {
if (x < 0 || x >= m || y < 0 || y >= n) {
return 0;
}
if (visited[x][y] || grid[x][y] == 0) {
return 0;
}

visited[x][y] = true;
int area = 1;

for (int k = 0; k < 4; k++) {
area += dfs(grid, x + dx[k], y + dy[k], visited);
}

return area;
}
}

为什么这里用返回值累加

因为面积本身就是一个可以递归合并的量。

当前格子面积为 1，四个方向的连通面积再累加上来，就是整个岛屿面积。

复杂度分析

• 时间复杂度：O(m * n)
• 空间复杂度：O(m * n)

DFS 不仅可以“标记走过”，也可以“返回一片连通区域的统计值”。

例题四：路径是否存在

题目：

从起点出发，判断是否能走到终点。

这类题常见于迷宫、网格路径、图可达性判断。

解题思路

DFS 的返回值可以直接表示：

从当前点出发，是否能到达目标点

如果某一条路径能到达目标，就直接返回 true。
否则继续搜索其他方向。

Java 代码实现

class Solution {
private int m;
private int n;
private int[] dx = {–1, 1, 0, 0};
private int[] dy = {0, 0, –1, 1};

public boolean hasPath(int[][] maze, int sx, int sy, int tx, int ty) {
m = maze.length;
n = maze[0].length;
boolean[][] visited = new boolean[m][n];
return dfs(maze, sx, sy, tx, ty, visited);
}

private boolean dfs(int[][] maze, int x, int y, int tx, int ty, boolean[][] visited) {
if (x == tx && y == ty) {
return true;
}
if (x < 0 || x >= m || y < 0 || y >= n) {
return false;
}
if (visited[x][y] || maze[x][y] == 1) {
return false;
}

visited[x][y] = true;

for (int k = 0; k < 4; k++) {
if (dfs(maze, x + dx[k], y + dy[k], tx, ty, visited)) {
return true;
}
}

return false;
}
}

为什么找到答案可以直接返回

因为这类题只关心：

有没有一条路能到终点

只要某个方向成功了，就没有必要继续搜索其他方向。

这也是 DFS 在“可达性判断”问题中的典型用法。

复杂度分析

• 时间复杂度：最坏 O(m * n)
• 空间复杂度：O(m * n)

如果题目只问“能不能到”，DFS 找到目标后可以立即返回。

DFS 和 BFS：该怎么区分

DFS 和 BFS 都是搜索算法，但适合场景不同。

怎么选

如果题目强调：

• 遍历所有连通区域
• 找一种路径是否存在
• 树的递归遍历
• 枚举所有可能路径

通常先考虑 DFS。

如果题目强调：

• 最短步数
• 最少操作次数
• 按层推进

通常先考虑 BFS。

DFS 适合深入搜索和连通性判断，BFS 适合最短步数和层次扩展。

常见坑点：DFS 最容易错在哪里

1. 忘记标记访问

如果不写：

visited[x][y] = true;

那么 DFS 可能在相邻格子之间反复横跳，陷入死循环。

2. 标记访问太晚

有些题中应该在进入节点后立刻标记。
如果先递归再标记，可能会重复进入同一个节点。

正确顺序通常是：

3. 越界判断写错

网格题里最常见的错误就是下标越界。

一定要先判断：

if (x < 0 || x >= m || y < 0 || y >= n)

再访问数组内容。

4. 四个方向写漏

二维网格通常要处理四个方向：

上、下、左、右

如果少写一个方向，搜索结果就不完整。

5. 递归太深导致栈溢出

在极端数据下，DFS 递归深度可能非常大。
如果题目规模很大，可能需要改成显式栈的迭代写法。

不过在大多数算法题中，递归 DFS 仍然是最常见、最清晰的写法。

DFS 迭代写法：用栈模拟递归

虽然递归 DFS 最常见，但也可以用栈来模拟。

import java.util.Stack;

class Solution {
public void dfsIterative(int[][] grid, int sx, int sy) {
int m = grid.length;
int n = grid[0].length;
int[] dx = {–1, 1, 0, 0};
int[] dy = {0, 0, –1, 1};
boolean[][] visited = new boolean[m][n];
Stack<int[]> stack = new Stack<>();

stack.push(new int[]{sx, sy});

while (!stack.isEmpty()) {
int[] cur = stack.pop();
int x = cur[0];
int y = cur[1];

if (x < 0 || x >= m || y < 0 || y >= n) {
continue;
}
if (visited[x][y] || grid[x][y] == 0) {
continue;
}

visited[x][y] = true;

for (int k = 0; k < 4; k++) {
stack.push(new int[]{x + dx[k], y + dy[k]});
}
}
}
}

这种写法和递归 DFS 的逻辑相同，只是把系统调用栈换成了手动维护的栈。

模板总结：DFS 题怎么写更稳

可以按这个顺序写 DFS：

一个通用模板是：

void dfs(状态) {
if (不合法 || 已访问) {
return;
}

标记当前状态;

for (下一个状态) {
dfs(下一个状态);
}
}

如果题目需要统计值，可以让 DFS 返回一个整数。
如果题目需要判断可达性，可以让 DFS 返回布尔值。

总结

DFS 是搜索题里非常基础的一种思路。
它的核心不是复杂代码，而是清晰地沿着一条路往深处走。

你可以重点记住下面几句话：

• DFS 适合连通块、路径、树和图的遍历
• DFS 通常用递归实现，也可以用栈模拟
• 网格 DFS 记住越界、访问标记和四个方向
• 连通块问题本质是“遇到一个新点就把整片区域标记掉”
• 路径存在性问题可以找到答案就立即返回
• DFS 和 BFS 的区别在于搜索策略不同
• 递归太深时要注意栈溢出风险

如果你已经掌握了递归和回溯，那么 DFS 基本就只是把“搜索对象”从排列组合换成网格、树和图。