如果你刷 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]改为'0' |
RecursionError | 递归深度超过 Python 限制 | 改用 BFS，或增大递归深度限制 |
| 两边陆地被算成一座 | 没有正确处理对角线 | 记住只检查上下左右四个方向 |
| 空网格报错 | grid[0]访问越界 | 在最前面判空 |
| 答案偏大 | 水格子被当成陆地处理 | 检查字符用的是'1'还是数字1 |
| BFS 运行超时 | 重复入队导致队列膨胀 | 入队时立刻标记为'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'、把统计数量换成统计最大面积、把静态地图换成动态添加陆地……每换一次，你对图论的理解就深一层。这就是这道母题真正值钱的地方。
