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

概述

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

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

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

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

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

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

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

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

1. DFS 是什么
2. DFS 的基本写法
3. 二维网格中的 DFS
4. 连通块和岛屿问题
5. 路径搜索问题
6. 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 结构是：

voiddfs(当前节点){if(终止条件){return;}标记当前节点;for(下一个节点:所有可行邻居){dfs(下一个节点);}}

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

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

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

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

网格 DFS 模板

voiddfs(intx,inty){if(越界||已访问||不满足条件){return;}标记访问;for(四个方向){dfs(nx,ny);}}

图 DFS 模板

voiddfs(intnode){if(已访问){return;}标记访问;for(intnext:graph[node]){dfs(next);}}

树 DFS 模板

voiddfs(TreeNoderoot){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 代码实现

classSolution{privateintm;privateintn;privateint[]dx={-1,1,0,0};privateint[]dy={0,0,-1,1};publicvoiddfs(char[][]grid,intx,inty,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(intk=0;k<4;k++){intnx=x+dx[k];intny=y+dy[k];dfs(grid,nx,ny,visited);}}}

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

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

如果没有先判断：

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

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

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

所以判断顺序通常是：

1. 越界
2. 是否访问过
3. 是否满足题目条件

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

例题二：岛屿数量

题目：

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

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

解题思路

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

做法是：

1. 遍历整个网格
2. 如果遇到一个未访问的1
3. 岛屿数量加一
4. 从这个点开始 DFS，把整个岛屿都标记掉

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

Java 代码实现

classSolution{privateintm;privateintn;privateint[]dx={-1,1,0,0};privateint[]dy={0,0,-1,1};publicintnumIslands(char[][]grid){if(grid==null||grid.length==0){return0;}m=grid.length;n=grid[0].length;boolean[][]visited=newboolean[m][n];intcount=0;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(!visited[i][j]&&grid[i][j]=='1'){count++;dfs(grid,i,j,visited);}}}returncount;}privatevoiddfs(char[][]grid,intx,inty,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(intk=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 代码实现

classSolution{privateintm;privateintn;privateint[]dx={-1,1,0,0};privateint[]dy={0,0,-1,1};publicintmaxAreaOfIsland(int[][]grid){m=grid.length;n=grid[0].length;boolean[][]visited=newboolean[m][n];intmaxArea=0;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(!visited[i][j]&&grid[i][j]==1){maxArea=Math.max(maxArea,dfs(grid,i,j,visited));}}}returnmaxArea;}privateintdfs(int[][]grid,intx,inty,boolean[][]visited){if(x<0||x>=m||y<0||y>=n){return0;}if(visited[x][y]||grid[x][y]==0){return0;}visited[x][y]=true;intarea=1;for(intk=0;k<4;k++){area+=dfs(grid,x+dx[k],y+dy[k],visited);}returnarea;}}

为什么这里用返回值累加

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

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

复杂度分析

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

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

例题四：路径是否存在

题目：

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

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

解题思路

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

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

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

Java 代码实现

classSolution{privateintm;privateintn;privateint[]dx={-1,1,0,0};privateint[]dy={0,0,-1,1};publicbooleanhasPath(int[][]maze,intsx,intsy,inttx,intty){m=maze.length;n=maze[0].length;boolean[][]visited=newboolean[m][n];returndfs(maze,sx,sy,tx,ty,visited);}privatebooleandfs(int[][]maze,intx,inty,inttx,intty,boolean[][]visited){if(x==tx&&y==ty){returntrue;}if(x<0||x>=m||y<0||y>=n){returnfalse;}if(visited[x][y]||maze[x][y]==1){returnfalse;}visited[x][y]=true;for(intk=0;k<4;k++){if(dfs(maze,x+dx[k],y+dy[k],tx,ty,visited)){returntrue;}}returnfalse;}}

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

因为这类题只关心：

有没有一条路能到终点

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

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

复杂度分析

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

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

DFS 和 BFS：该怎么区分

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

怎么选

如果题目强调：

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

通常先考虑 DFS。

如果题目强调：

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

通常先考虑 BFS。

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

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

1. 忘记标记访问

如果不写：

visited[x][y]=true;

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

2. 标记访问太晚

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

正确顺序通常是：

1. 判断合法性
2. 标记访问
3. 继续搜索邻居

3. 越界判断写错

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

一定要先判断：

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

再访问数组内容。

4. 四个方向写漏

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

上、下、左、右

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

5. 递归太深导致栈溢出

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

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

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

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

importjava.util.Stack;classSolution{publicvoiddfsIterative(int[][]grid,intsx,intsy){intm=grid.length;intn=grid[0].length;int[]dx={-1,1,0,0};int[]dy={0,0,-1,1};boolean[][]visited=newboolean[m][n];Stack<int[]>stack=newStack<>();stack.push(newint[]{sx,sy});while(!stack.isEmpty()){int[]cur=stack.pop();intx=cur[0];inty=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(intk=0;k<4;k++){stack.push(newint[]{x+dx[k],y+dy[k]});}}}}

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

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

可以按这个顺序写 DFS：

1. 明确当前状态是什么
2. 明确什么时候停止搜索
3. 明确怎么标记访问
4. 明确下一步要搜索哪些方向
5. 明确是否需要返回值

一个通用模板是：

voiddfs(状态){if(不合法||已访问){return;}标记当前状态;for(下一个状态){dfs(下一个状态);}}

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

总结

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

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

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

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