如果你刚开始刷算法题一定绕不开两个词DFS 和 BFS。而提到 DFS深度优先搜索的入门题几乎所有刷题群的首选都是「岛屿数量」。原因很简单题目完全不绕弯但 DFS 的核心要素全都有——二维网格转图、递归探索、访问标记、边界判断、复杂度分析一道题全部讲清楚。我这些年带过不少新人每次都是从这道题起步今天把完整的拆解、代码和踩坑记录写下来。1. 为什么「岛屿数量」是入门DFS的最佳载体1.1 题目到底在问什么先看题面。LeetCode 200 的输入是一个二维数组里面只有1和0两种字符1表示陆地0表示海水。你只需要数一数这里面有几座岛。所谓「一座岛」就是上下左右四个方向连成一片的1组成的区域斜对角相邻不算同一座岛。举个例子grid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ]左上角两块1连在一起算一座岛中间的单个1是一座岛右下角的两个1也算一座岛所以答案是 3。题目边界很明确m和n最大到 300意味着整个网格最多 90000 个格子这个规模决定了普通的深度优先搜索完全够用不会超时。这也是为什么它适合入门——数据范围给你留足了空间去关注算法本身而不是一上来就抠性能优化。1.2 为什么图论的直觉在这里最清晰很多人第一次看到这道题会懵DFS 不是处理树和图吗二维数组里哪来的树其实把网格转译成图就清楚了。每个格子是图上的一个节点上下左右四个方向上相邻的格子就是节点的边。于是「数岛屿」就变成了「数连通分量」——有多少块节点彼此之间能通过边连成一个整体。图论里的连通性问题DFS 是最直接的解法。它的核心思路就一句话见到一块陆地就沿着上下左右把所有能连到的陆地全部走一遍把它们标记成已经访问过然后数量加一。重复这个动作直到整个网格扫完。我再打个比方。你周末去一个群岛旅游想数清楚这个群岛有几座岛正常的做法是什么先飞到一座岛上沿着步道把整座岛从头到尾走一遍走完在清单上打一个勾再去下一座岛。「走遍一座岛」的过程就是一次 DFS把脚踩过的所有陆地都记下来防止重复走就是访问标记。这比任何抽象的算法描述都好懂。1.3 为什么首选DFS而不是BFS或并查集同样能解这道题的还有 BFS广度优先搜索和并查集。但作为入门题DFS 的优势太明显了。BFS 思路也不难但它需要额外引入一个队列去管理「当前层的节点」很多新手会卡在「什么时候出队、什么时候入队、为什么要用 queue 而不是 stack」这些细节上。DFS 则不同递归本身就是天然的栈结构你只需要关心「当前格子该干什么」剩下的交给递归去处理代码量大幅缩短。并查集是另一种很优雅的解法通过不断合并相邻陆地来统计连通分量。但这东西涉及路径压缩、按秩合并等一堆概念对于刚接触算法的人来说理解成本比 DFS 高一个量级。更适合作为岛屿数量的进阶解法去探索而不是入门第一课。所以我的建议很明确第一遍做这道题老老实实用 DFS把搜索思维建立起来。BFS 和并查集可以留到后面再对比学习第 4 节我会单独讲 DFS 和 BFS 的差异。2. DFS核心思想拆解递归、栈与访问标记2.1 递归的过程一条路走到黑再回头DFS 在网格里的行为模式本质上就是「一条路走到黑」。从当前陆地出发先一直往上走走不了就往右再走不了就往下、往左直到四个方向全部走不通才回退到上一个岔路口换一个方向继续尝试。我以最典型的递归代码来拆这个行为def dfs(r, c): if 越界 or grid[r][c] 0: return grid[r][c] 0 # 标记已访问 dfs(r - 1, c) # 上 dfs(r 1, c) # 下 dfs(r, c - 1) # 左 dfs(r, c 1) # 右当程序执行dfs(0, 0)时它会先进入dfs(-1, 0)发现越界立刻返回再进入dfs(1, 0)而dfs(1, 0)又会试图执行dfs(0, 0)发现已经被标记为0了直接返回。你看这就像在迷宫里做记号每走一个格子就标记一次重复走过的路直接被跳过。这个过程用函数调用栈来解释更加本质。每次调用dfs系统都会把当前函数的状态压入调用栈子调用返回后再弹栈继续执行当前函数剩余的部分。所以递归版的 DFS 不需要你手动维护任何数据结构系统已经在背后帮你维护了一个栈。2.2 访问标记DFS真正必须做对的一件事初学者最容易忽略的就是访问标记。如果 DFS 过程中不做任何标记会发生什么我拿一个最简单的 2x2 网格来演示1 1 1 1从左上角进入dfs(0, 0)然后调用dfs(0, 1)接着dfs(0, 1)会调用dfs(0, 0)而dfs(0, 0)又会调用dfs(0, 1)……两个格子互相调用永不停止最后程序直接栈溢出崩溃。所以「标记已访问」不是可选项而是 DFS 的灵魂。标记方式有三种常见选择方案做法优点缺点原地修改把访问过的1改成0实现最简单无需额外空间会修改输入数组visited 数组新建一个二维布尔数组记录访问状态不破坏原始数据额外需要 O(mn) 空间哈希集合用 Set 存访问过的坐标思路直观常数较大代码稍长最推荐的还是原地修改。虽然它改变了输入但在面试或竞赛场景下先跟面试官确认一句「我假设允许修改原数组」大多数时候都能过关。如果题目明确不允许修改输入再退回到 visited 数组方案也不麻烦。2.3 递归的代价函数调用栈与空间复杂度讲 DFS 的空间复杂度很多人只记得结论是 O(mn)但不知道为什么。原因在于递归调用的深度。最坏情况是整个网格全是陆地比如 300 x 300 的全部1。从第一个格子开始 DFS它会沿着一条路径一直往深处钻最多可能要递归 90000 层才会开始逐层返回。每一层函数调用都会占用栈空间所以空间复杂度是 O(mn)。时间上每个格子最多被访问一次每次访问执行常数次操作总时间复杂度是 O(mn)。这个复杂度已经是最优的了因为每个格子你至少得看一次才能决定它是不是岛屿的一部分。有一点需要提醒你递归深度达到 90000在 C/C 里通常还能撑住但 Python 默认的递归深度限制是 1000所以用 Python 写这道题时很多人会加一行sys.setrecursionlimit(1000000)关于这一点第 3 节我会再细说。3. 多种语言代码落地方案与要点3.1 C语言递归版LeetCode标准接口C 语言版本最贴近 LeetCode 原始接口也最适合理解内存上发生了什么。完整的题解函数如下void dfs(char** grid, int gridSize, int* gridColSize, int r, int c) { int rows gridSize; int cols gridColSize[0]; // 越界或者遇到海水直接返回 if (r 0 || r rows || c 0 || c cols || grid[r][c] 0) { return; } // 标记当前格子为已访问 grid[r][c] 0; // 四个方向继续深搜 dfs(grid, gridSize, gridColSize, r - 1, c); dfs(grid, gridSize, gridColSize, r 1, c); dfs(grid, gridSize, gridColSize, r, c - 1); dfs(grid, gridSize, gridColSize, r, c 1); } int numIslands(char** grid, int gridSize, int* gridColSize) { if (gridSize 0 || gridColSize[0] 0) { return 0; } int rows gridSize; int cols gridColSize[0]; int count 0; for (int r 0; r rows; r) { for (int c 0; c cols; c) { if (grid[r][c] 1) { count; dfs(grid, gridSize, gridColSize, r, c); } } } return count; }两个细节值得注意。第一gridColSize是一个数组在 LeetCode 这道题里每一行的列数相同所以直接用gridColSize[0]即可。不过这是一道约定俗成的前提实际写代码时如果有不确定的输入格式最好先确认。第二我习惯把边界判断放在函数最开始而不是在调用前判断这样每个方向的调用都先自我检查代码更简洁也不容易漏。3.2 Python版面试写起来最快的版本Python 的优势是代码量极小逻辑清晰特别适合在面试时快速手写。核心代码如下from typing import List class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 def dfs(r: int, c: int) - None: if r 0 or r rows or c 0 or c cols or grid[r][c] 0: return grid[r][c] 0 dfs(r - 1, c) dfs(r 1, c) dfs(r, c - 1) dfs(r, c 1) for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 dfs(r, c) return count这里有个关键点Python 的嵌套函数会自动捕获外层变量rows、cols、grid所以不需要像 C 语言那样把一堆参数传进函数里。但这也意味着如果你修改了rows或cols的值可能会触发 Python 的闭包作用域规则所以我在函数开头把它们存成局部变量避免后续踩坑。如果你在本地跑且网格特别大建议在文件开头加上import sys sys.setrecursionlimit(1000000)不设置的话遇到全陆地的大网格Python 会直接抛RecursionError。LeetCode 的 Python 环境本身已经放宽了限制但本地调试时很容易遇到这个问题。3.3 Java版工程习惯最接近的版本Java 版的写法和 C 很接近但更符合面向对象习惯。我给出最常见的实现class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int rows grid.length; int cols grid[0].length; int count 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } private void dfs(char[][] grid, int r, int c) { if (r 0 || r grid.length || c 0 || c grid[0].length || grid[r][c] 0) { return; } grid[r][c] 0; dfs(grid, r - 1, c); dfs(grid, r 1, c); dfs(grid, r, c - 1); dfs(grid, r, c 1); } }Java 里最容易犯的错是grid[0].length在grid为空时直接抛空指针所以我把判空放在最前面。另外这道题输入是char[][]字符1和字符串1完全不同写的时候别搞混。3.4 迭代栈版不用递归也能实现DFS有些面试官会问「能不能不用递归实现 DFS」这时候你要知道递归的本质是系统帮你维护调用栈手动实现只需要自己维护一个显式栈即可。下面用 Python 展示这个思路class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 grid[r][c] 0 stack [(r, c)] while stack: x, y stack.pop() for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 0 stack.append((nx, ny)) return count迭代版有一个极其重要的细节必须在入栈的同时标记访问而不是出栈时才标记。如果出栈时才标记一个格子可能被多个邻居重复入栈导致大量冗余遍历严重时甚至会退化成指数级复杂度。这个版本代码上比递归版长但好处是不会有递归深度过大的问题。在 C 语言等系统栈空间受限的场景下迭代栈版更稳健。4. DFS与BFS的对比、选型与回溯澄清4.1 BFS解法的完整实现既然热搜里总把 DFS 和 BFS 放在一起这里就顺便把 BFS 版岛屿数量的代码也交出来方便你对比from collections import deque from typing import List class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 grid[r][c] 0 q deque([(r, c)]) while q: x, y q.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 0 q.append((nx, ny)) return countDFS 用栈递归本身就是栈BFS 用队列这是两者最表面的区别。但我建议你在理解上去看更本质的差异DFS 是「一个方向钻到底再回来」BFS 是「一圈一圈往外扩散」。就好比打扫整栋楼DFS 是把一个房间彻底收拾完再去隔壁BFS 是先把所有房间的门都擦一遍再擦第二层的窗户逐层推进。4.2 DFS与BFS的选型对比我整理了下面这个对照表遇到搜索类题目直接套维度DFSBFS数据结构栈或递归队列实现难度递归写法很短需要显式 queue空间复杂度最坏 O(mn)常见分析为 O(min(m,n))典型场景连通性判断、路径枚举、回溯最短路径、层级遍历、拓扑排序是否爆栈递归深度大时可能爆不存在爆栈问题判断用哪种记住一个简单标准求最短路径优先考虑 BFS数连通块、枚举所有可能路径优先考虑 DFS。比如这道岛屿数量DFS 和 BFS 都能做但 DFS 写起来短所以入门首选 DFS。而像「从左上角到右下角的最短步数」这种题DFS 要搜索所有路径才能确认最短路径效率极低必须用 BFS。4.3 DFS与回溯别把这道题当成回溯题热搜里常出现「dfs回溯」这个词很多人会把 DFS 和回溯混为一谈这里必须澄清。回溯Backtracking可以理解为「DFS 状态恢复」。它的典型流程是尝试一个选择进入下一层返回后再撤销这个选择以便尝试其他分支。经典的回溯题是全排列。当你选了数字 1 放在第一位递归下去等所有以 1 开头的排列都枚举完了必须把 1 从当前集合里移除才能尝试以 2 开头的排列。这里的「移除」就是状态恢复。那岛屿数量为什么不是回溯因为访问过的陆地你不需要恢复成1它已经被计入当前岛屿了之后不会再被任何其他岛屿使用。你可以这么判断如果一道题需要「用完再还」那大概率是回溯如果「用完就丢」那就是普通 DFS。很多初学者在做全排列、子集、N 皇后时被回溯绕晕回头再看岛屿数量会觉得 DFS 也没那么难。所以把这道题放在回溯题之前刷还有一层降维打击的效果。5. 常见问题排查与进阶刷题路线5.1 高频错误速查表我搜集了新人刷这道题最常踩的坑列成一张速查表错误现象根本原因解决办法数组越界异常递归前没检查边界或方向计算错误在递归函数第一行统一做边界判断程序死循环 / 栈溢出没有标记已访问格子每次访问后立即把1改成0结果偏大把相邻岛重复计数确认每次触发 DFS 只 count 一次且 DFS 会清理整块区域空输入直接崩溃没判空就访问grid[0]函数开头先处理grid为空或行列为 0 的情况Python 报 RecursionError递归深度超过默认限制sys.setrecursionlimit(1000000)迭代版结果不对出栈时才标记访问改为入栈时立即标记其中「迭代版入栈时标记」是最反直觉的一条。很多人觉得我压进栈的格子肯定会被处理晚一点标记有什么关系关系很大——同一个格子可能被多个邻居同时发现如果等出栈才标记它会被重复压入栈很多次整个搜索会变得极其低效。5.2 做完这道题后建议立刻刷的三道变体岛屿数量是搜索题的基础款刷完它别急着走立刻做这几道变体才能把 DFS 吃透。第一道是 LeetCode 695「岛屿的最大面积」。它只改了一个地方不再是统计岛屿数量而是返回面积最大的那座岛有多大。做法几乎一模一样只是把 DFS 的返回值从void改成int每次递归返回周围面积加一。这道题能帮你加深「递归返回值」的掌控感。第二道是 LeetCode 130「被围绕的区域」。这题的技巧在于直接从边界开始 DFS把所有和边界连通的O先标记成特殊字符然后整个网格再扫一遍把没标记的O全改成X。做完这道题你会明白DFS 不一定要从每个格子发起也可以只在某些特定起点发起。第三道是 LeetCode 417「太平洋大西洋水流问题」。它需要从两个海洋边界分别做 DFS记录哪些格子能流到太平洋哪些能流到大西洋最后取交集。这道题引入了「逆向思维」——从目标点反向搜索而不是从起点正向搜索。难度比岛屿数量高一档但核心还是 DFS。三连刷下来你会对搜索题的变式套路很有感觉改返回值、改起点、改方向、改状态存储本质并没有变。5.3 现场手撕时的实战技巧最后说几个我面试和带人时积累的实际经验。第一先想清楚再动笔。写代码前用几句话把思路讲清楚先扫描所有格子遇到1就数量加一然后从这个点开始 DFS 把整座岛标记成0。面试官听到这句话一般心里已经给你加分了。第二方向数组能帮大忙。很多人喜欢单独写四行递归调用当变种题有八个方向时代码就爆炸了。我更推荐预先定义directions [(1,0), (-1,0), (0,1), (0,-1)]然后循环处理这样代码更短也方便扩展到八方向场景。第三主动交代复杂度。写完代码后主动说一句「每个格子最多访问一次所以时间是 O(mn)递归栈最坏 O(mn)」。这个习惯在面试中非常加分因为大部分人都要等面试官追问才说。第四关于修改原数组最好提前沟通。如果面试官明确要求不能修改输入第一时间切换到 visited 数组方案不要犹豫。这说明你考虑问题周全不是只会背模板。我自己刷这道题的经历也很说明问题。第一次做的时候照着网上的答案抄了一遍当时觉得自己懂了结果过了两天再写连方向数组都写不利索。后来我强制自己用三种方式分别实现了一遍——递归版、迭代栈版、BFS 版再把每版的时间空间复杂度自己推一遍才算真正理解。现在每次带新人刷题我都让他们做同样的练习先不看答案写出一种解法再强迫自己换一种写法。这个过程看起来很笨但真的比刷十道新题都有用。岛屿数量这道题好就好在它足够简单简单到可以把所有注意力都放在搜索本身。练完之后你会发现后面再碰到什么「单词接龙」「腐烂的橘子」「朋友圈找并集」脑子里出现的不再是恐惧而是清晰的搜索路径。祝你刷题顺利。