从第一次在力扣刷到第200题“岛屿数量”开始我就知道这道题不简单。它表面上是让你数一数二维网格里有几块连在一起的陆地实际上是经典的 Flood Fill洪水填充问题也是网格类图搜索的入门必修课。无论你准备面试用 DFS、BFS 还是并查集来解决这题都能一次考察你的图论基础、递归能力和边界条件意识。今天我就把三种解法的细节、易错点、实测经验全部捋一遍希望能帮你把这题吃透。1. 题目解读与核心思路拆解1.1 题目到底在问什么题目给你一个 m x n 的二维网格里面只有1和0两种字符1代表陆地0代表水。要求你数出网格中岛屿的数量而“岛屿”的定义是上下左右四个方向相邻的陆地连在一起形成的一个连通块就算一个岛屿。注意这里的几个关键限定。第一网格是字符类型不是数字判断的时候要用grid[i][j] 1不是 1很多第一次刷的人就在这里翻车。第二相邻方向只有四个上、下、左、右不考虑斜对角。如果斜对角也算相邻题目会明确说明没有说默认就是不连通的。第三网格外面的区域也就是越过边界的部分全部可以理解为水。这题最贴近生活的类比就是“扫雷”里的连通区域判断。你在网格里点中一块陆地跟它上下左右粘在一起的所有陆地都是同一个岛屿的一部分。从一个点出发把所有能连通的陆地全部标记掉计数加一再去找下一块还没被碰过的陆地重复这个过程最后得到的计数就是岛屿数量。1.2 为什么它是面试高频题这道题在力扣“热门 100 题”里长期占着一个位置不是因为难而是因为它太适合做区分度了。它看起来简单到新手也能读懂但真正写起来立刻就能看出一个人对图遍历的理解深度。大部分人第一反应都是 DFS递归往四个方向走把走过的陆地改成水。这个思路对不对对但光是 DFS 就能引出至少三个问题递归深度会不会爆栈、什么时候标记访问、要不要额外开 visited 数组。如果改成 BFS又要考虑队列里什么时候去重是入队时标记还是出队时标记。再往上还有并查集解法涉及怎么把二维坐标映射成一维编号、怎么维护连通分量数量。一个候选人能把这题做到什么程度面试官基本就能判断出他的算法水平在哪个档位。而且这题背后是网格类图搜索的通用套路做完这题之后“岛屿的最大面积”“被围绕的区域”“统计子岛屿”这些题的核心框架都可以直接复用。与其说你在刷一道题不如说你在打一个题型的基础。1.3 三种主流解法选型对比在动键盘之前先把思路理清楚。解决这道题本质上是“找连通分量”的过程遍历每一个格子遇到没访问过的陆地就计数加一然后把这块陆地所在的整个连通分量全部标记为已访问。标记访问的方式有两条路线。路线一是“原地标记”直接把访问过的1改成0相当于把整个岛淹掉这种做法的好处是不用额外开数组空间复杂度低坏处是会修改原始输入。如果面试官要求不能修改原数组就得开一个同尺寸的 visited 布尔数组。路线二是“额外标记”适合需要保留原始数据的场景。解法核心思路时间复杂度空间复杂度适合场景DFS 递归递归向四方向搜索遇水返回O(mn)O(mn) 最坏递归栈深度面试最容易写适合小规模网格BFS 队列用队列逐层扩散先标记再入队O(mn)O(mn) 队列最坏宽度不用递归避免栈溢出并查集陆地之间实现动态合并统计连通分量O(mn * α(mn))O(mn)需要频繁动态合并的场景理论进阶三道解法的本质都是把二维网格抽象成图每个格子是一个节点上下左右相邻的陆地之间有一条边。岛屿数量就是图中陆地节点的连通分量数量。理解了这个抽象后面所有代码都是围绕它展开的。2. DFS 解法最直观也最常写的方案2.1 递归版 DFS 设计思路DFS 的思路可以这样理解我在网格里溜达遇到一块陆地先把它标记为水然后接着去查看它的上、下、左、右邻居如果邻居也是陆地继续标记、继续深入直到所有能走到的陆地都被处理完这时候这一整个连通分量就算被“淹”掉了。这里最核心的一个点就是“先标记再递归”。不要等到递归调用的开头再去标记否则可能出现问题。比如某个格子被第一次访问后进入递归另一条路径又访问到它时如果没有提前标记就会重复进入同一个格子导致无限递归。所以代码结构里应该是先判断这个格子是不是越界、是不是水如果不是水立即把它改成水然后再递归四个方向。递归终止条件也很自然如果i或j越出边界或者当前格子已经不是陆地直接返回。这里有个容易被忽略的细节判断是不是陆地不能光看值等于1还可以先修改再判断这也是为什么很多标准题解会先写if grid[i][j] ! 1: return然后再修改。2.2 参考代码与逐行解读class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) def dfs(i: int, j: int) - None: if i 0 or i m or j 0 or j n or grid[i][j] ! 1: return grid[i][j] 0 dfs(i - 1, j) dfs(i 1, j) dfs(i, j - 1) dfs(i, j 1) count 0 for i in range(m): for j in range(n): if grid[i][j] 1: count 1 dfs(i, j) return count主循环里每次遇到一个1计数加一然后调用 DFS 把这一整块连通陆地全部淹掉。外层循环继续往后扫遇到已经被淹掉的格子就跳过遇到新的陆地再计数。整个过程不会漏掉任何一个孤立的岛屿也不会把同一个岛屿算两次。有人会问为什么不是四个方向每个都判断一下越界因为统一的越界判断放在递归函数开头更简洁而且递归深度少写四遍重复代码。不过熟悉性能优化的人可能会说每次递归都做四次边界判断会不会浪费实际上这种开销微不足道面试尺度下完全不需要纠结。2.3 递归深度风险与改良方案DFS 递归看起来简洁但有一个现实问题如果网格特别大比如 200 x 200最深递归路径可能达到 40000 层。Python 默认递归深度是 1000超过这个上限会直接抛RecursionError代码在力扣的大数据用例里就会挂。所以用 Python 写递归 DFS 时我一般会在本地测试先确认用例规模必要时通过sys.setrecursionlimit(10000)调大递归限制。但这只是治标不治本更好的做法是改成“显式栈”的 DFS用列表模拟系统递归栈。这样既保留了深度优先的搜索顺序又不会遇到递归深度限制。class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] count 0 for i in range(m): for j in range(n): if grid[i][j] 1: count 1 grid[i][j] 0 stack [(i, j)] while stack: x, y stack.pop() for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 1: grid[nx][ny] 0 stack.append((nx, ny)) return count这段代码本质上就是把递归改成手写栈每次遇到陆地先标记再把它压入栈里后续循环时又从栈里弹出来继续扩展。注意标记动作要发生在压栈之前否则同一个节点可能被重复压入栈导致不必要的重复遍历极端情况下还会让性能劣化。3. BFS 解法用队列改写避开递归深度3.1 为什么还要单独掌握 BFSDFS 虽然直观但很多人在面试时被追问“如果网格特别大你会怎么做”这时候如果能流畅切换到 BFS会是一个不错的加分点。BFS 的核心是用队列逐层扩散先从起点出发把周围一圈陆地全部找出来逐层往外推。它跟我们日常理解的“感染传播”很像一个细胞感染了相邻细胞相邻细胞再感染它们的邻居。BFS 的好处是不会涉及系统递归栈也就没有递归深度溢出的风险。空间上最坏情况是队列里同时存在很多节点当网格全是陆地时BFS 的队列宽度可能达到 O(mn)但实际测试里它通常很稳。还有个容易被忽视的点BFS 能天然地处理“最短路径”一类的问题虽然这题不用算距离但练好 BFS 的队列操作习惯后面刷“腐烂的橘子”“单词接龙”这些题会顺手很多。3.2 BFS 参考代码与核心细节from collections import deque class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) dirs [(-1, 0), (1, 0), (0, -1), (0, 1)] count 0 for i in range(m): for j in range(n): if grid[i][j] 1: count 1 grid[i][j] 0 q deque([(i, j)]) while q: x, y q.popleft() for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 1: grid[nx][ny] 0 q.append((nx, ny)) return count对比显式栈 DFS 的代码BFS 只改了两处把stack [(i, j)]换成q deque([(i, j)])把pop()换成popleft()。但这两处改动决定了遍历顺序完全不同一个是深度优先一个是广度优先。BFS 里有一个非常经典的坑如果你在弹出节点时才标记为已访问而不是在加入队列时标记同一个陆地节点可能会被多个邻居重复加入队列。比如节点 A 和 B 都是陆地且相邻先从起点加入了 A 和 B处理 A 时发现 B 还是1又把 B 加入了一次队列。正确做法是在 push 进队列的那一刻就把格子改成水保证每个格子最多入队一次。这个细节值得在任何讨论 BFS 的场合单独强调因为它直接影响时间复杂度和正确性。3.3 方向数组与坐标技巧方向数组是省事又不容易错的写法把四个方向的偏移量统一放在一个列表里循环里统一处理。相比写四行dfs(i-1, j)之类的代码方向数组在需要改方向时特别方便比如以后遇到“八个方向相邻”的问题只需要把数组扩展成八项。dirs [(-1, 0), (1, 0), (0, -1), (0, 1)]边界判断用0 nx m and 0 ny n这种区间比较是网格类题目的通用写法比nx 0 and nx m更整洁。写多了之后会形成肌肉记忆但刚开始一定要提醒自己先判边界再取grid[nx][ny]顺序反了就会出现索引越界。坐标映射方面二维坐标(i, j)可以映射到一维编号i * n j这个技巧在并查集解法里是必须的在 BFS 和 DFS 里虽然不必要但提前理解了后面看并查集代码才不会懵。4. 并查集解法进阶面试加分项4.1 并查集为什么也能解这题并查集Union-Find解决的是“动态连通性”问题。把这题的网格想成一张图每个陆地格子是一个节点相邻陆地之间有一条边。初始时每个节点单独一个连通分量然后我们遍历所有相邻的陆地节点对把它们合并到同一个分量里。最后统计陆地节点构成的连通分量数量就是岛屿数量。用并查集最大的优势在于它是增量式合并适合边遍历边合并的场景。如果数据是动态变化的比如之后新增了一块陆地问你现在的岛屿数量是多少并查集可以很方便地“在线”处理。这虽然不是本题的考点但却是面试官喜欢深入追问的扩展点。并查集的路径压缩和按秩合并两大优化也不复杂路径压缩把树的深度压到接近常数按秩合并保证树不会退化成链表。加上这两个优化之后单次 find 和 union 的操作时间可以认为是近似 O(1)整体复杂度接近 O(mn)。4.2 参考代码与映射细节class UnionFind: def __init__(self, n: int): self.parent list(range(n)) self.rank [0] * n self.count n def find(self, x: int) - int: while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, x: int, y: int) - None: rx, ry self.find(x), self.find(y) if rx ry: return if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 self.count - 1 class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) water 0 uf UnionFind(m * n) for i in range(m): for j in range(n): if grid[i][j] 0: water 1 continue idx i * n j if i 1 m and grid[i 1][j] 1: uf.union(idx, (i 1) * n j) if j 1 n and grid[i][j 1] 1: uf.union(idx, i * n j 1) return uf.count - water这段代码思路是并查集初始把所有格子包括水都当成独立节点所以count初始是 m * n。遍历过程中遇到水就把water加一遇到陆地只向右方和下方合并即可因为左上方的两个方向在之前遍历时已经处理过不会漏也不会重复。最后count里包含的总连通分量数减去水的数量剩下的就是陆地的连通分量数。另一种更直接的写法是只给陆地节点建并查集初始 count 设为陆地数量每次合并两个不同分量时 count 减一。两种写法结果一样前者代码更通用后者逻辑更贴近“岛屿”语义。面试时我推荐按后一种思路讲代码更简单不容易绕晕如果讲前者更体现你对并查集内部结构的理解。4.3 并查集在面试中的定位并查集解法通常不是面试本题的第一选择但它是一个很好的“第二方案”。当你把 DFS 写完之后如果面试官追问“有没有别的思路”这时候抛出并查集说明你不仅会套模板还理解图连通性的本质。但注意不要一上来就写并查集。这道题用 DFS 和 BFS 已经足够高效并查集代码量更大单独为了刷题没必要第一个写。不过如果你是准备简历上写“熟悉图论算法”的候选人能在本题主动提及并查集并且讲清原理会给人眼前一亮的感觉。如果以后刷到“547. 省份数量”这类题你会惊喜地发现它和岛屿数量几乎是同一个模型省份就是连通分量城市之间的连接关系就是相邻关系。那时候并查集就是你优先选择的解法。5. 边界条件、常见错误与面试实战心得5.1 高频坑点清单这题我前前后后刷过好几遍也帮别人 review 过不少代码总结出的坑点基本集中在下面这些地方。第一个空网格和没有陆地的特殊情况。grid可以是空列表也可以是[[]]这时候直接返回 0 就完事。很多人的解法没有处理not grid[0]在len(grid[0])这里直接崩了。第二个字符类型判断。输入是List[List[str]]如果拿数字的思维去比较会一直得不到匹配导致计数永远为 0。虽然题目明确写了是字符但本地自测时不小心用整型构造测试数据也会中招。第三个修改输入数组的问题。原地标记1为0很方便但如果面试官明确说不能破坏原始网格你就必须准备一个 visited 布尔数组。visited 的逻辑和原地标记基本一样只是在判断时把grid[nx][ny] 1改成grid[nx][ny] 1 and not visited[nx][ny]标记时把 visited 置为 True。第四个BFS 入队时没有立即标记。这个问题前面反复强调过出现频率极高。不加立即标记的后果是所有相邻的陆地都会被重复入队很多次运行时间可能会变成指数级才更可怕的是死循环。第五个递归爆栈。Python 默认递归深度只有 1000遇到大网格递归 DFS 直接崩掉。面试时如果用的语言有系统递归栈限制还没等面试官追问你的代码可能已经跑挂了。所以不少人在面试现场会选择显式栈 DFS 或 BFS。第六个并查集坐标映射混淆。二维坐标(i, j)映射到一维编号是i * n j注意是列数 n不是行数 m。如果网格不是正方形拿 m 去乘会算错编号后续合并就会把不该合并的节点连在一起。5.2 实测经验与性能对比我本地用 300 x 300 的全陆地网格测试过三种解法的表现。DFS 递归在 Python 里需要先把sys.setrecursionlimit调大到 100000 才能跑完整体耗时反而没有 BFS 稳。BFS 和显式栈 DFS 的耗时接近都在几十毫秒量级比递归 DFS 要稳定很多。并查集的代码量最大运行时间也会比 BFS 略慢一些但差距不明显因为路径压缩后每个操作都接近常数。实际刷题时最常见的还是用 BFS 或 DFS 的原地标记法理由是代码短、思路清晰、时间空间复杂度都能被面试官接受。并查集适合当作“加分项”出现在口头分析里不一定要真的写完整。如果你在面试里遇到这题我建议的节奏是先跟面试官确认两个问题输入是否可能为空、是否允许修改原数组。然后直接说思路“遍历每个格子遇到未访问的陆地就从它出发做一次搜索把整个连通块标记掉计数加一最后返回计数。”接着选 DFS 讲写法同时提一句“如果担心递归深度可以用 BFS 或显式栈替代”。这个回答框架既不啰嗦又展示了你的工程思维。5.3 从这题延伸出去的变体题岛屿数量是一整个题型族的源头做熟它之后下面几道题可以按顺序刷。“695. 岛屿的最大面积”在 DFS/BFS 遍历时顺手统计连通块大小取最大值即可。“1254. 统计封闭岛屿的个数”多一个条件如果岛屿挨着网格边界就不算封闭处理办法是优先把边界上的陆地全部淹掉再统计内部剩下的岛屿。“1905. 统计子岛屿”把两个网格的连通关系联合判断考验你对多次搜索的并联能力。“130. 被围绕的区域”更接近 Flood Fill 的本意从边界出发标记所有能到达的区域剩下的陆地就全是被包围的。这些题核心套路都一致掌握了第 200 题后面基本就是加条件、换场景。最后分享一个我实际用下来的心得不要只背一种解法就觉得自己会了这题。第一次刷的时候我 DFS 写完就急着过下一题结果一个多月后再遇到岛屿类变体手生得厉害。后来老老实实把 DFS、BFS、并查集三种写法都手写了一遍再刷变体题就跟开了锁一样。建议你也试试哪怕并查集只是照着写一遍理解深度都会完全不同。