如果你刷 LeetCode 已经有一段时间大概率会碰上这道题——200. 岛屿数量。它属于“一看题面就懂、一写代码就卡”的典型代表给你一个二维网格里面用1表示陆地、0表示水让你数出有多少座岛屿。听起来像小学数图形题但它背后藏着的是图论中的连通性问题是 DFS、BFS、并查集三大基本功的绝佳练兵场也是面试中用来快速判断候选人“有没有真写过代码”的一道高频题。这道题在 LeetCode 热门 100 题里常年占据一席之地出题人基本不会改头换面大厂面试手撕环节也经常直接原题上阵。它的适用范围非常广不论你是刚入门数组和递归的初学者还是已经在准备系统设计面试的中级工程师都能在这道题里找到值得打磨的东西。这篇文章我会直接讲透岛屿数量的四种主流解法包括 DFS、BFS、并查集的完整代码以及我在实际刷题和面试过程中踩过的坑、总结出的避雷经验。看完之后你不仅能 AC 这道题还能顺手秒掉腐烂的橘子、被围绕的区域、岛屿周长这一整条题单。1. 题目理解与核心算法选型1.1 题面到底在问什么先花三十秒钟把题面嚼碎。给你一个m x n的二维字符网格每个格子要么是1陆地要么是0水。岛屿的定义是由连续的陆地格子组成且上下左右四个方向相邻算作“连接”。对角线方向不算这是最容易搞错的第一点。举个例子11110 11010 11000 00000这个网格里只有一座岛因为左上角那一大块1通过上下左右连接在一起。再看这个11000 11000 00100 00011有三个岛左上角一个中间一个右下角一个。中间那个孤零零的1尽管周围都是水但它是陆地区域所以单独算一座岛。这个问题的本质是在一个网格图中找出所有连通块的数量。把每个陆地格子看成图里的一个节点上下左右相邻的陆地之间连一条边那你要求的岛屿数量就是图中连通分量的个数。一旦想清楚这一点解法就变得很清晰遍历每个格子遇到陆地就计数加一然后把这块陆地“感染”成水并继续感染它上下左右相邻的陆地直到一整块陆地全部变成水再继续遍历下一个格子。1.2 为什么这道题在面试里出镜率那么高我的看法是这道题考察的核心能力刚好踩在“基础”和“实战”的交界线上。第一它考察你对图论基本概念的理解。很多初学者以为图一定要长成V个点和E条边的邻接表形式遇到网格就懵了。实际上网格图是最容易理解的图每个格子有固定的四个邻居。能识别出这个抽象过程说明你具备把现实问题建模成算法问题的能力。第二它考察 DFS 和 BFS 的熟练度。两种遍历方式都能解决而且实现起来都不长但恰恰是这种“短代码”最能暴露你对递归出口、边界判断、访问标记这些细节是否敏感。第三它给了你展示进阶知识的机会。比如并查集解法、原地标记优化、空间复杂度优化都是你在面试中体现深度的地方。同样的题基础的人能 AC有经验的人能讲出一套方法论这就是高频题的价值所在。1.3 拿到题后正确的第一思路是什么不要一上来就写代码。先问自己三个问题这个网格是什么结构——是个隐式图节点是格子边是上下左右相邻关系。我要去重吗——当然要否则同一片陆地会被重复计数所以我需要标记访问过的格子。有没有可能不需要额外空间——能直接把访问过的1改成0也就是“原地沉没”。想明白这三点解法就自然而然浮出水面外层循环遍历所有格子内层遇到1就计数并触发一次“感染”过程把所有连在一起的1都变成0。感染过程可以用递归DFS也可以用队列BFS甚至可以用并查集从连通性角度做。下面逐一展开。2. 四种实现方案的完整代码与原理剖析2.1 DFS 递归实现最直觉的“洪水填充”DFS 版本的思路是最贴近人类直觉的。想象你在一个棋盘上踩到一个陆地格子然后你向四个方向疯狂蔓延逢陆就踩踩完就标记为水直到你脚下再也没有可踩的陆地这时一片岛屿就被你“淹”掉了。整个过程像洪水漫灌所以也常常被称为 Flood Fill。直接看代码from typing import List class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid: 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] 0: return # 把当前陆地标记为水防止重复遍历 grid[i][j] 0 # 递归淹没上下左右四个方向 dfs(i - 1, j) dfs(i 1, j) dfs(i, j - 1) dfs(i, j 1) island_count 0 for i in range(m): for j in range(n): if grid[i][j] 1: island_count 1 dfs(i, j) return island_count这里最关键的细节是grid[i][j] 0。如果把这行去掉你会陷入无限递归因为相邻的陆地互相调用谁都没有被标记循环永远无法终止。这也是经典错误之一后面我会单独列出来。DFS 的优点是代码短、逻辑直观、面试时讲起来行云流水。缺点也同样明显当网格非常大的时候Python 的递归深度默认只有 1000 左右如果一整片陆地的大小超过这个深度就会直接抛出RecursionError。尽管 LeetCode 本题的数据范围是m, n 300理论上整张地图全是陆地时 DFS 深度能达到 90000极限情况下确实存在爆栈风险。我实测时发现官方测试用例里大部分情况不会触发但在199x199全陆地之类的手工用例上Python 默认配置下会挂。因此刷题阶段可以用面试手撕时我更推荐 BFS或者在 DFS 之前加一句sys.setrecursionlimit(1000000)兜底。2.2 BFS 迭代实现更稳更通用的工程化选择BFS 的思路同样简单遇到陆地就计数然后把它放进队列一层一层向外扩散。扩散过的格子立刻标记为水避免同一块陆地被反复入队。BFS 版本代码from typing import List from collections import deque class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid: return 0 m, n len(grid), len(grid[0]) island_count 0 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] for i in range(m): for j in range(n): if grid[i][j] 1: island_count 1 queue deque([(i, j)]) grid[i][j] 0 # 入队即标记防止重复入队 while queue: x, y queue.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 1: grid[nx][ny] 0 queue.append((nx, ny)) return island_count这里我特别想强调一个细节标记的时机是入队时而不是出队时。很多人第一次写 BFS 时会在popleft()之后才标记grid[nx][ny] 0这样会导致同一个格子被重复加入队列多次虽然结果可能不错但时间和空间都会浪费极端情况下还会导致队列膨胀。正确姿势是一旦发现邻居是陆地立刻标记并入队。BFS 最大的优势是天然避免递归深度问题因为队列是显式维护的不依赖函数调用栈。而且它的扩展过程是一层一层向外的在某些需要计算“到陆地的最短距离”的变体题里BFS 是唯一正确的选择。比如 LeetCode 994 腐烂的橘子本质上就是多源 BFS如果你岛屿数量的 BFS 写法已经烂熟于心那道题基本就是换个包装。2.3 并查集实现从连通性本质出发的方案并查集解法是很多面试官喜欢的加分项。因为它直接抓住了问题的本质——数连通分量。思路是这样初始化每个格子为一个独立集合然后把所有相邻的陆地合并到同一个集合里最后统计陆地中有多少个不同的集合根节点就是岛屿数量。from typing import List class UnionFind: def __init__(self, n: int): self.parent list(range(n)) self.rank [0] * n def find(self, x: int) - int: if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩 return self.parent[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 class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid: return 0 m, n len(grid), len(grid[0]) uf UnionFind(m * n) water_count 0 for i in range(m): for j in range(n): if grid[i][j] 0: water_count 1 else: 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) total m * n roots set() for i in range(total): roots.add(uf.find(i)) return len(roots) - water_count并查集解法最核心的优化有两个路径压缩和按秩合并。路径压缩让find的均摊时间复杂度接近 O(1)按秩合并则保证树的深度不会退化。两者配合才能让整个算法的复杂度稳定在近似 O(m×n) 的水平。这个解法的代码量比 DFS/BFS 都要长面试时如果时间不够我通常建议先写 DFS/BFS然后再补充说明“如果改用并查集也能做核心思路是把陆地合并到同一个集合”。真正动手写并查集通常出现在更大规模的动态连通性问题里比如“岛屿数量 II”这种一边加陆地一边查数量的题那才是并查集的主场。2.4 三种方案的取舍对照方案时间复杂度空间复杂度代码量面试推荐度适用场景DFS 递归O(m×n)O(m×n) 最坏递归栈最短高容易讲清思路小数据量、教学演示BFS 迭代O(m×n)O(min(m,n)) 队列宽度短最高稳定不爆栈常规数据、工程实践并查集O(m×n × α(m×n))O(m×n)较长加分项动态加陆地的变体题我这里把 BFS 的空间复杂度标成 O(min(m,n))因为队列中最多同时存放一层的节点而网格层的宽度不会超过较短的那条边。DFS 递归栈的最坏深度是整张图全是陆地的情况那就是 O(m×n)。不过在实际面试中你把 DFS 或 BFS 的空间复杂度说成 O(m×n) 通常也能接受关键是别说出“O(1)”这种一听就没算过的答案。3. 复杂度推导、边界条件与实战踩坑记录3.1 时间复杂度与空间复杂度怎么算才算严谨先说时间复杂度。无论 DFS 还是 BFS外层两层循环会把每个格子至少访问一次这是 O(m×n)。在感染过程中每个被感染的格子最多被上下左右四个方向检查一次但感染的前提是它还没有被标记成水所以每个格子最多被真正处理一次。综合来看总操作次数是网格规模的常数倍因此时间复杂度是O(m×n)其中 m 是行数n 是列数。并查集的时间复杂度稍微复杂一点。初始化时遍历所有格子是 O(m×n)每对相邻陆地都做一次union和若干次find。因为路径压缩和按秩合并的存在可以认为单次操作的均摊时间接近 O(α(V))其中 α 是阿克曼函数的反函数实际值小到可以当常数看。所以总复杂度可以表述为O(m×n × α(m×n))面试时直接说近似 O(m×n) 问题不大但如果你能补一句“路径压缩后接近线性”会显得更有深度。空间复杂度要分情况。DFS 递归解法在最坏情况下整张网格全是陆地递归深度达到 m×n所以空间复杂度 O(m×n)。BFS 的队列在最坏情况下也可能会存储不少节点但通常不会超过 O(min(m,n))为了保险很多题解直接写 O(m×n) 也不算错。并查集需要parent和rank两个数组大小都是 m×n所以是 O(m×n)。3.2 边界测试用例清单刷题最忌讳的就是“示例能过就万事大吉”。我的习惯是写完代码后立刻跑一组边界用例这里分享一份我常用的清单用例输入期望结果考察点空网格[]0处理空输入只有水[000]0无岛屿只有陆地[111]1全连通单行[101]2单行场景单列[1,0,1]2单列场景对角相邻[10,01]2对角线不算连通全陆地大矩阵[111,111,111]1防止重复计数对角线用例特别值得留意。很多人受平面几何直觉影响觉得斜对角的两块陆地应该算同一座岛。但题面明确写了“水平方向或竖直方向上相邻”所以(0,0)和(1,1)的两个1永远不连通。这一类细节在变体题里同样重要比如计算岛屿周长时四条边中只有和水或者网格边界相接的边才算周长如果没搞清楚相邻规则周长肯定算错。3.3 我实际踩过的三个坑第一个坑是递归爆栈。我在本地用 Python 测试一个250×250的全陆地网格时DFS 版本直接抛了RecursionError。这不代表 LeetCode 官方用例一定会触发但它真实存在。解决方案要么把递归深度调大要么直接用 BFS。我个人更推荐 BFS因为面试现场你不可能去改sys.setrecursionlimit写一个不依赖递归深度的解法最稳妥。第二个坑是标记时机不对。我第一次写 BFS 的时候习惯在出队时才把当前格子改成水结果导致同一片陆地被反复入队。表面上看最终计数没错但队列会膨胀到难以接受的程度而且在变体题里会导致严重超时。后来我养成了一个条件反射任何格子一旦进入队列就立刻标记访问过。这个习惯在 BFS 类的所有题目里都管用。第三个坑是直接把参数当成局部变量时忘了 Python 里二维数组是引用传递。grid作为列表传入函数你在内部修改它外部其实是看得到的。很多人用 DFS 时确实利用了这个特性做原地标记这没问题。但如果你在做“需要保留原地图”的变体题时比如复制网格再处理就要注意深浅拷贝的问题否则一个不小心就把原数据弄丢了。3.4 常见问题速查表现象可能原因解决办法递归无限循环没有标记已访问陆地在进入递归前将grid[i][j]改为0RecursionError递归深度超过 Python 限制改用 BFS或增大递归深度限制两边陆地被算成一座没有正确处理对角线记住只检查上下左右四个方向空网格报错grid[0]访问越界在最前面判空答案偏大水格子被当成陆地处理检查字符用的是1还是数字1BFS 运行超时重复入队导致队列膨胀入队时立刻标记为0关于第五个坑我必须单独强调一下是字符串1和0不是整数1和0。新手最容易犯的错就是把grid[i][j] 1当成判断条件结果所有格子都被当成水输出永远是 0。这个低级错误一旦在面试中出现印象分基本清零。写代码前最好扫一眼题面给的数据类型。4. 热门变体题、面试表达技巧与刷题路线建议4.1 一道题串起一类题从岛屿数量到腐烂的橘子岛屿数量这题真正厉害的地方在于它是一个“母题”。把它的解法稍微改一改就能打通一大批面试题。先说 LeetCode 994 腐烂的橘子。这道题给了你一个网格2代表腐烂的橘子1代表新鲜的橘子每分钟腐烂橘子会感染上下左右相邻的新鲜橘子问多少分钟后所有新鲜橘子都腐烂或者永远不可能。这题本质上就是多源 BFS先把所有腐烂的橘子放入队列然后一层一层向外扩散记录扩散层数。你会惊讶地发现它的骨架和岛屿数量的 BFS 解法几乎一样不同的只是初始入队的条件从“遇到陆地”变成了“遇到腐烂橘子”以及遍历结束后需要检查还有没有新鲜橘子剩余。再看被围绕的区域130 题。它要求把被X包围的O全部变成X但边界上的O及其连通区域不能被改。这题的思路是反过来做先从边界上的O出发做 DFS 或 BFS把它们标记成特殊字符比如#然后遍历整个网格把所有剩余的O改成X再把#还原成O。这也是 Flood Fill 思想的直接应用。还有岛屿周长463 题。这题甚至不需要数联通块只需要遍历每个陆地数它四周有几个方向是水或者边界。每遇到一个“邻居是水”的边周长就加一。你看还是那套网格遍历和方向判断的技巧。如果把这一串题放到一起刷你会发现它们的核心全是“在网格图上做遍历 标记状态”。一旦把岛屿数量吃透后续这些题基本是送分题。4.2 面试现场怎么讲这道题才能拿高分面试和刷题有一点本质区别刷题追求 AC面试追求“过程有逻辑、代码有亮点”。这道题如果你只是背答案背下来面试官一问“为什么 BFS 空间复杂度是 O(min(m,n))”可能就露馅了。我的建议是采用“三段式”讲法第一段讲建模。拿到题后先告诉面试官“网格可以看成一个带隐式边的图每个陆地块是节点上下左右四条边定义邻接关系。所以我要求的东西是连通分量个数。”第二段讲思路演进。先说最直观的 DFS每碰到陆地就 DFS 淹掉整块。然后补充一句“为了防止递归爆栈工程上我会改成 BFS队列显式控制遍历层。如果需要动态加陆地用并查集更合适。”第三段讲细节。主动提到标记访问、入队即标记、四个方向的边界判断这些细节会立刻让面试官觉得你是真的写过这道题而不是背过答案。另外有一个加分小技巧在写完 DFS 后主动问一句“需要我改成 BFS 版本吗”这比闷头写完一种解法然后说“写完了”要好得多。面试官通常很乐意看到候选人主动展示第二种思路。4.3 从这道题出发的刷题路线建议如果你正在准备面试我建议把岛屿数量作为图论刷题的起点。整体路线可以这样安排先把 DFS 和 BFS 的模板各写三遍直到能不假思索写出四个方向偏移和边界检查。做 200. 岛屿数量然后用它当模板做 695. 岛屿的最大面积在 DFS 中顺便统计面积、463. 岛屿周长统计边界的特殊条件。再进阶到 994. 腐烂的橘子练习多源 BFS 和分层扩散。然后做 130. 被围绕的区域训练反向思维从边界出发做 Flood Fill。如果还有余力看一眼 305. 岛屿数量 II这道题就是并查集的典型应用能帮你把并查集真正用熟。这条路线题量不算大大概 6 道题但能把网格图这一类的套路全部打通。很多人在 LeetCode 热门 100 题里反复刷却始终感觉没进步问题就出在“同一类题没有集中消化”。用母题串起变体题是我个人用过最有效的刷题方式。最后再分享一个小经验刷题时不要只盯着 AC 那个瞬间。AC 之后花五分钟想想“如果我把某个条件换一下这道题会变成什么”这种思维训练比多刷十道新题都管用。岛屿数量这题尤其适合做这种假想——把1换成2、把统计数量换成统计最大面积、把静态地图换成动态添加陆地……每换一次你对图论的理解就深一层。这就是这道母题真正值钱的地方。