概述学完回溯之后我们继续看另一个非常重要的搜索思想DFS深度优先搜索。很多初学者会把 DFS 和回溯混在一起。它们确实很像因为回溯本身就常常是 DFS 的一种应用。但 DFS 的关注点更广通常是沿着一条路尽可能往深处走走不通再回退换另一条路DFS 最常见的使用场景包括二维网格搜索连通块统计岛屿问题路径是否存在树的遍历图的遍历这类题的共同点是需要从一个起点出发把能到达的地方全部走一遍。如果你已经学过递归和回溯那么 DFS 会非常自然。它通常可以直接用递归写也可以用显式栈写。这篇文章会围绕 DFS 的基础形态展开DFS 是什么DFS 的基本写法二维网格中的 DFS连通块和岛屿问题路径搜索问题DFS 的常见坑点学完这篇你应该能把 DFS 视为一种标准搜索手段并能写出网格遍历、连通块统计和路径搜索的基础代码。核心概念DFS 到底是什么DFS 的全称是Depth First Search中文叫深度优先搜索。它的核心思想是先沿着一条路径一直走到尽头再回头尝试其他路径这和广度优先搜索BFS正好相对。BFS是一层一层扩展DFS是一条路走到底。DFS 的典型过程假设从点A出发周围可以走到B、C、DA - 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(rootnull){return;}dfs(root.left);dfs(root.right);}DFS 的核心不是代码形式而是思路从当前点出发判断是否可以继续标记当前状态递归访问下一个位置DFS 的代码一般都长得很像关键是判断条件、访问标记和下一步搜索方向。例题一二维网格中的 DFS 遍历二维网格题是 DFS 的经典入门场景。题目可以抽象成给定一个二维网格从某个起点出发访问所有满足条件的格子。例如网格中有0和11 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(x0||xm||y0||yn){return;}if(visited[x][y]||grid[x][y]0){return;}visited[x][y]true;for(intk0;k4;k){intnxxdx[k];intnyydy[k];dfs(grid,nx,ny,visited);}}}为什么要先判断越界和访问状态网格搜索里最常见的错误就是越界。如果没有先判断if(x0||xm||y0||yn)那么后续访问grid[x][y]时就会报错。如果不判断visited[x][y]DFS 可能会在相邻格子之间来回走形成死循环。所以判断顺序通常是越界是否访问过是否满足题目条件二维网格 DFS 的关键是方向枚举、越界判断和访问标记。例题二岛屿数量题目给定一个由1和0组成的二维网格1表示陆地0表示海水求岛屿的数量。岛屿定义为上下左右相连的陆地块。解题思路这道题本质上是统计网格中有多少个连通块。做法是遍历整个网格如果遇到一个未访问的1岛屿数量加一从这个点开始 DFS把整个岛屿都标记掉这样每个岛屿只会统计一次。Java 代码实现classSolution{privateintm;privateintn;privateint[]dx{-1,1,0,0};privateint[]dy{0,0,-1,1};publicintnumIslands(char[][]grid){if(gridnull||grid.length0){return0;}mgrid.length;ngrid[0].length;boolean[][]visitednewboolean[m][n];intcount0;for(inti0;im;i){for(intj0;jn;j){if(!visited[i][j]grid[i][j]1){count;dfs(grid,i,j,visited);}}}returncount;}privatevoiddfs(char[][]grid,intx,inty,boolean[][]visited){if(x0||xm||y0||yn){return;}if(visited[x][y]||grid[x][y]0){return;}visited[x][y]true;for(intk0;k4;k){dfs(grid,xdx[k],ydy[k],visited);}}}为什么 DFS 后岛屿只会统计一次假设一个岛屿里有多个相连的11 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){mgrid.length;ngrid[0].length;boolean[][]visitednewboolean[m][n];intmaxArea0;for(inti0;im;i){for(intj0;jn;j){if(!visited[i][j]grid[i][j]1){maxAreaMath.max(maxArea,dfs(grid,i,j,visited));}}}returnmaxArea;}privateintdfs(int[][]grid,intx,inty,boolean[][]visited){if(x0||xm||y0||yn){return0;}if(visited[x][y]||grid[x][y]0){return0;}visited[x][y]true;intarea1;for(intk0;k4;k){areadfs(grid,xdx[k],ydy[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){mmaze.length;nmaze[0].length;boolean[][]visitednewboolean[m][n];returndfs(maze,sx,sy,tx,ty,visited);}privatebooleandfs(int[][]maze,intx,inty,inttx,intty,boolean[][]visited){if(xtxyty){returntrue;}if(x0||xm||y0||yn){returnfalse;}if(visited[x][y]||maze[x][y]1){returnfalse;}visited[x][y]true;for(intk0;k4;k){if(dfs(maze,xdx[k],ydy[k],tx,ty,visited)){returntrue;}}returnfalse;}}为什么找到答案可以直接返回因为这类题只关心有没有一条路能到终点只要某个方向成功了就没有必要继续搜索其他方向。这也是 DFS 在“可达性判断”问题中的典型用法。复杂度分析时间复杂度最坏O(m * n)空间复杂度O(m * n)如果题目只问“能不能到”DFS 找到目标后可以立即返回。DFS 和 BFS该怎么区分DFS 和 BFS 都是搜索算法但适合场景不同。对比项DFSBFS搜索方式一路深入一层一层扩展常见实现递归或栈队列适合题型连通块、路径枚举、树遍历最短步数、层次遍历结果特点不保证最短通常适合最短路的无权图场景怎么选如果题目强调遍历所有连通区域找一种路径是否存在树的递归遍历枚举所有可能路径通常先考虑 DFS。如果题目强调最短步数最少操作次数按层推进通常先考虑 BFS。DFS 适合深入搜索和连通性判断BFS 适合最短步数和层次扩展。常见坑点DFS 最容易错在哪里1. 忘记标记访问如果不写visited[x][y]true;那么 DFS 可能在相邻格子之间反复横跳陷入死循环。2. 标记访问太晚有些题中应该在进入节点后立刻标记。如果先递归再标记可能会重复进入同一个节点。正确顺序通常是判断合法性标记访问继续搜索邻居3. 越界判断写错网格题里最常见的错误就是下标越界。一定要先判断if(x0||xm||y0||yn)再访问数组内容。4. 四个方向写漏二维网格通常要处理四个方向上、下、左、右如果少写一个方向搜索结果就不完整。5. 递归太深导致栈溢出在极端数据下DFS 递归深度可能非常大。如果题目规模很大可能需要改成显式栈的迭代写法。不过在大多数算法题中递归 DFS 仍然是最常见、最清晰的写法。DFS 迭代写法用栈模拟递归虽然递归 DFS 最常见但也可以用栈来模拟。importjava.util.Stack;classSolution{publicvoiddfsIterative(int[][]grid,intsx,intsy){intmgrid.length;intngrid[0].length;int[]dx{-1,1,0,0};int[]dy{0,0,-1,1};boolean[][]visitednewboolean[m][n];Stackint[]stacknewStack();stack.push(newint[]{sx,sy});while(!stack.isEmpty()){int[]curstack.pop();intxcur[0];intycur[1];if(x0||xm||y0||yn){continue;}if(visited[x][y]||grid[x][y]0){continue;}visited[x][y]true;for(intk0;k4;k){stack.push(newint[]{xdx[k],ydy[k]});}}}}这种写法和递归 DFS 的逻辑相同只是把系统调用栈换成了手动维护的栈。模板总结DFS 题怎么写更稳可以按这个顺序写 DFS明确当前状态是什么明确什么时候停止搜索明确怎么标记访问明确下一步要搜索哪些方向明确是否需要返回值一个通用模板是voiddfs(状态){if(不合法||已访问){return;}标记当前状态;for(下一个状态){dfs(下一个状态);}}如果题目需要统计值可以让 DFS 返回一个整数。如果题目需要判断可达性可以让 DFS 返回布尔值。总结DFS 是搜索题里非常基础的一种思路。它的核心不是复杂代码而是清晰地沿着一条路往深处走。你可以重点记住下面几句话DFS 适合连通块、路径、树和图的遍历DFS 通常用递归实现也可以用栈模拟网格 DFS 记住越界、访问标记和四个方向连通块问题本质是“遇到一个新点就把整片区域标记掉”路径存在性问题可以找到答案就立即返回DFS 和 BFS 的区别在于搜索策略不同递归太深时要注意栈溢出风险如果你已经掌握了递归和回溯那么 DFS 基本就只是把“搜索对象”从排列组合换成网格、树和图。
第18篇-DFS深度优先搜索-从二维网格到路径搜索
概述学完回溯之后我们继续看另一个非常重要的搜索思想DFS深度优先搜索。很多初学者会把 DFS 和回溯混在一起。它们确实很像因为回溯本身就常常是 DFS 的一种应用。但 DFS 的关注点更广通常是沿着一条路尽可能往深处走走不通再回退换另一条路DFS 最常见的使用场景包括二维网格搜索连通块统计岛屿问题路径是否存在树的遍历图的遍历这类题的共同点是需要从一个起点出发把能到达的地方全部走一遍。如果你已经学过递归和回溯那么 DFS 会非常自然。它通常可以直接用递归写也可以用显式栈写。这篇文章会围绕 DFS 的基础形态展开DFS 是什么DFS 的基本写法二维网格中的 DFS连通块和岛屿问题路径搜索问题DFS 的常见坑点学完这篇你应该能把 DFS 视为一种标准搜索手段并能写出网格遍历、连通块统计和路径搜索的基础代码。核心概念DFS 到底是什么DFS 的全称是Depth First Search中文叫深度优先搜索。它的核心思想是先沿着一条路径一直走到尽头再回头尝试其他路径这和广度优先搜索BFS正好相对。BFS是一层一层扩展DFS是一条路走到底。DFS 的典型过程假设从点A出发周围可以走到B、C、DA - 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(rootnull){return;}dfs(root.left);dfs(root.right);}DFS 的核心不是代码形式而是思路从当前点出发判断是否可以继续标记当前状态递归访问下一个位置DFS 的代码一般都长得很像关键是判断条件、访问标记和下一步搜索方向。例题一二维网格中的 DFS 遍历二维网格题是 DFS 的经典入门场景。题目可以抽象成给定一个二维网格从某个起点出发访问所有满足条件的格子。例如网格中有0和11 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(x0||xm||y0||yn){return;}if(visited[x][y]||grid[x][y]0){return;}visited[x][y]true;for(intk0;k4;k){intnxxdx[k];intnyydy[k];dfs(grid,nx,ny,visited);}}}为什么要先判断越界和访问状态网格搜索里最常见的错误就是越界。如果没有先判断if(x0||xm||y0||yn)那么后续访问grid[x][y]时就会报错。如果不判断visited[x][y]DFS 可能会在相邻格子之间来回走形成死循环。所以判断顺序通常是越界是否访问过是否满足题目条件二维网格 DFS 的关键是方向枚举、越界判断和访问标记。例题二岛屿数量题目给定一个由1和0组成的二维网格1表示陆地0表示海水求岛屿的数量。岛屿定义为上下左右相连的陆地块。解题思路这道题本质上是统计网格中有多少个连通块。做法是遍历整个网格如果遇到一个未访问的1岛屿数量加一从这个点开始 DFS把整个岛屿都标记掉这样每个岛屿只会统计一次。Java 代码实现classSolution{privateintm;privateintn;privateint[]dx{-1,1,0,0};privateint[]dy{0,0,-1,1};publicintnumIslands(char[][]grid){if(gridnull||grid.length0){return0;}mgrid.length;ngrid[0].length;boolean[][]visitednewboolean[m][n];intcount0;for(inti0;im;i){for(intj0;jn;j){if(!visited[i][j]grid[i][j]1){count;dfs(grid,i,j,visited);}}}returncount;}privatevoiddfs(char[][]grid,intx,inty,boolean[][]visited){if(x0||xm||y0||yn){return;}if(visited[x][y]||grid[x][y]0){return;}visited[x][y]true;for(intk0;k4;k){dfs(grid,xdx[k],ydy[k],visited);}}}为什么 DFS 后岛屿只会统计一次假设一个岛屿里有多个相连的11 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){mgrid.length;ngrid[0].length;boolean[][]visitednewboolean[m][n];intmaxArea0;for(inti0;im;i){for(intj0;jn;j){if(!visited[i][j]grid[i][j]1){maxAreaMath.max(maxArea,dfs(grid,i,j,visited));}}}returnmaxArea;}privateintdfs(int[][]grid,intx,inty,boolean[][]visited){if(x0||xm||y0||yn){return0;}if(visited[x][y]||grid[x][y]0){return0;}visited[x][y]true;intarea1;for(intk0;k4;k){areadfs(grid,xdx[k],ydy[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){mmaze.length;nmaze[0].length;boolean[][]visitednewboolean[m][n];returndfs(maze,sx,sy,tx,ty,visited);}privatebooleandfs(int[][]maze,intx,inty,inttx,intty,boolean[][]visited){if(xtxyty){returntrue;}if(x0||xm||y0||yn){returnfalse;}if(visited[x][y]||maze[x][y]1){returnfalse;}visited[x][y]true;for(intk0;k4;k){if(dfs(maze,xdx[k],ydy[k],tx,ty,visited)){returntrue;}}returnfalse;}}为什么找到答案可以直接返回因为这类题只关心有没有一条路能到终点只要某个方向成功了就没有必要继续搜索其他方向。这也是 DFS 在“可达性判断”问题中的典型用法。复杂度分析时间复杂度最坏O(m * n)空间复杂度O(m * n)如果题目只问“能不能到”DFS 找到目标后可以立即返回。DFS 和 BFS该怎么区分DFS 和 BFS 都是搜索算法但适合场景不同。对比项DFSBFS搜索方式一路深入一层一层扩展常见实现递归或栈队列适合题型连通块、路径枚举、树遍历最短步数、层次遍历结果特点不保证最短通常适合最短路的无权图场景怎么选如果题目强调遍历所有连通区域找一种路径是否存在树的递归遍历枚举所有可能路径通常先考虑 DFS。如果题目强调最短步数最少操作次数按层推进通常先考虑 BFS。DFS 适合深入搜索和连通性判断BFS 适合最短步数和层次扩展。常见坑点DFS 最容易错在哪里1. 忘记标记访问如果不写visited[x][y]true;那么 DFS 可能在相邻格子之间反复横跳陷入死循环。2. 标记访问太晚有些题中应该在进入节点后立刻标记。如果先递归再标记可能会重复进入同一个节点。正确顺序通常是判断合法性标记访问继续搜索邻居3. 越界判断写错网格题里最常见的错误就是下标越界。一定要先判断if(x0||xm||y0||yn)再访问数组内容。4. 四个方向写漏二维网格通常要处理四个方向上、下、左、右如果少写一个方向搜索结果就不完整。5. 递归太深导致栈溢出在极端数据下DFS 递归深度可能非常大。如果题目规模很大可能需要改成显式栈的迭代写法。不过在大多数算法题中递归 DFS 仍然是最常见、最清晰的写法。DFS 迭代写法用栈模拟递归虽然递归 DFS 最常见但也可以用栈来模拟。importjava.util.Stack;classSolution{publicvoiddfsIterative(int[][]grid,intsx,intsy){intmgrid.length;intngrid[0].length;int[]dx{-1,1,0,0};int[]dy{0,0,-1,1};boolean[][]visitednewboolean[m][n];Stackint[]stacknewStack();stack.push(newint[]{sx,sy});while(!stack.isEmpty()){int[]curstack.pop();intxcur[0];intycur[1];if(x0||xm||y0||yn){continue;}if(visited[x][y]||grid[x][y]0){continue;}visited[x][y]true;for(intk0;k4;k){stack.push(newint[]{xdx[k],ydy[k]});}}}}这种写法和递归 DFS 的逻辑相同只是把系统调用栈换成了手动维护的栈。模板总结DFS 题怎么写更稳可以按这个顺序写 DFS明确当前状态是什么明确什么时候停止搜索明确怎么标记访问明确下一步要搜索哪些方向明确是否需要返回值一个通用模板是voiddfs(状态){if(不合法||已访问){return;}标记当前状态;for(下一个状态){dfs(下一个状态);}}如果题目需要统计值可以让 DFS 返回一个整数。如果题目需要判断可达性可以让 DFS 返回布尔值。总结DFS 是搜索题里非常基础的一种思路。它的核心不是复杂代码而是清晰地沿着一条路往深处走。你可以重点记住下面几句话DFS 适合连通块、路径、树和图的遍历DFS 通常用递归实现也可以用栈模拟网格 DFS 记住越界、访问标记和四个方向连通块问题本质是“遇到一个新点就把整片区域标记掉”路径存在性问题可以找到答案就立即返回DFS 和 BFS 的区别在于搜索策略不同递归太深时要注意栈溢出风险如果你已经掌握了递归和回溯那么 DFS 基本就只是把“搜索对象”从排列组合换成网格、树和图。
