岛屿数量题解：DFS、BFS与并查集三种算法详解

做算法题这么多年力扣 200 题“岛屿数量”大概是互联网技术面试里出场率最高的图论入门题。题目本身不长给你一个由 1 和 0 组成的二维网格1 是陆地、0 是水上下左右相邻的 1 属于同一座岛要你数出网格里一共有多少座岛屿。就这么一句话背后其实串起了 DFS、BFS、并查集三套完整的算法体系。我刷这题前后刷了三遍第一遍只会写递归第二遍才理解为什么 BFS 能抗住超大规模用例第三遍用并查集重写时才真正想明白“连通分量”到底是什么。这篇文章把这三遍的收获和踩过的坑一次讲完准备面试刷题的朋友可以直接照着练。1. 这道题考什么从题意到图论建模1.1 原题描述与输入输出细节原题干不长给你一个由1陆地和0水组成的二维网格计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。直接读题有四个细节经常被忽略。第一输入是字符1和0不是整数 1 和 0意味着你在 Python 里写grid[i][j] 1永远不成立判断必须是1我第一次用 Java 刷时也踩过char 1的坑。第二岛屿由“上下左右”相邻的陆地构成是四方向连通不是八方向更不是对角线也算。很多人刷到后面变种题“岛屿的周长”时把斜对角也算进去整个答案就跑偏了。第三“网格的四条边均被水包围”这句话是在告诉我们不需要单独处理边界外的虚拟水域越界直接停止探索即可不用给网格额外加一圈0。第四岛屿数量的本质是统计连通分量个数同样的思路换个问法从“统计多少块”变成“统计最大的一块多大”就是力扣 695 岛屿的最大面积。这题输出要求很简单返回一个整数即可。但正因为输入输出看起来平平无奇面试官才有空间在“怎么遍历、怎么标记、怎么优化空间”这三个点上层层追问把它变成一道可深可浅的经典题。1.2 网格即图的映射思路很多人第一次看到这题会懵二维数组遍历我懂但这跟图有什么关系其实网格天然就是一张图每个格子是一个节点上下左右相邻的格子之间有一条无向边。只不过这张图没有用邻接表存储而是用坐标索引节点(i, j)的邻居就是(i-1, j)、(i1, j)、(i, j-1)、(i, j1)唯一的额外工作就是判断坐标是否越界。做这个映射之后问题立刻变得清晰“岛屿”就是由若干1节点组成的连通分量岛屿数量就是这张“网格图”里所有由1构成的连通分量的个数。于是问题变成一个很标准的图论问题给定一张图统计满足某种条件的连通分量数量。树的遍历、图的遍历在这里全部适用DFS 前序遍历、BFS 层序扩展、并查集合并三套方案都能解时间复杂度也都是 O(m×n)其中 m 是行数、n 是列数。我在带新人时有个习惯只要看到“二维矩阵 连通块 数量/面积/边界”这三个关键词的组合直接往图论上靠大概率没错。这道题就是这种思维模式的最佳训练场。1.3 为什么它是面试高频题这题能成为高频题我认为有三个原因。一是代码量小主函数加一个辅助函数大约二十行面试官有足够时间在写完之后继续追问而不是看候选人憋半天代码二是它同时考察了二维数组坐标处理、递归或迭代遍历、以及“如何标记已访问”这个基础能力一个知识点能挖出好几个层面的问题三是它变种极多问完这题面试官可以顺理成章接着问“最大面积”“周长”“被围绕的区域”整套考察闭环非常成熟。我自己面试别人时也爱用这题尤其是让候选人讲思路而不是直接写代码。能说出“把每个格子看成图的节点”的人和图论有关的后续问题基本都能聊下去只会背模板的人在问到“为什么这里要把1改成0”的时候通常就会卡壳。这也是我建议每个准备算法面试的人都把这题吃透的根本原因。2. 三种主流解法DFS、BFS、并查集2.1 DFS把“访问过”写进网格里DFS 的思路可以用一句话概括遍历网格中的每个格子一旦遇到1就说明发现了一座新岛屿计数器加 1然后递归地把这座岛上所有相邻的1全部标记成0。这样后续遍历不会再碰到这座岛的任何部分自然就不会重复计数。很多初学者会问为什么要把1改成0而不是单独维护一个 visited 二维数组因为这道题允许修改原输入原地改数组既省了一张同样大小的布尔表又把“访问过”和“原来是水”统一处理了判断条件就可以简化为grid[i][j] 1。但如果你面对的是不允许修改输入的场景或者面试官明确说“不要改变原数组”那就得换 visited 方案代价是多一个 O(m×n) 的布尔数组空间。递归版本实现简单理解起来也直观但它有一个隐患当网格是一个全1的超大矩阵时递归深度可能达到 m×n 的级别。Python 默认递归深度大约 1000C 的调用栈虽然深一些但也不是无限。力扣的测试数据里确实存在这种极端用例所以后面我会讲怎么换成 BFS 或手动栈来规避。2.2 BFS迭代版避免递归栈溢出BFS 是 DFS 的迭代替代方案核心逻辑是遇到1时先把它改成0并入队然后循环弹出队首坐标把它的四个相邻格子中仍是1的全部改成0并入队。这样一层层向外扩展直到队列为空说明这座岛已经完全被“淹没”。这里有一个新手最容易犯的错只在出队时才标记格子为0导致同一个格子被多个邻居重复入队。举个简单例子一个三格连成 L 形的岛如果出队时才标记中间的格子可能被左边和上边同时加入队列队列里出现大量重复坐标轻则多做无效循环重则死循环。正确做法是“入队即标记”也就是在把邻居加入队列的那一刻就把它改成0保证每个节点最多入队一次。BFS 的优势在于没有递归栈溢出风险而且在窄长的网格上队列长度很可控。实际刷题时如果题目数据范围很大我一般优先写 BFS稳。2.3 并查集把连通问题交给数据结构并查集是第三条路也是最能体现数据结构思维的做法。思想是给每个格子分配一个从 0 到 m×n-1 的唯一编号编号公式是行号 × 总列数 列号然后扫描网格对于每一个1格子尝试把它与上方、左方的1邻居合并。初始时把并查集的计数器设为陆地的总数每成功合并一次计数器减 1最终计数器的值就是岛屿数量。这里有一个自然的问题为什么合并时只需要看上方和左方因为扫描方向是逐行从左到右、从上到下每个格子的上、左邻居如果存在1那么这两条边已经覆盖了所有横向和纵向的相邻关系。右边和下边的邻居在当前格子被扫描到的时候还没有处理但等扫描到那个邻居时它自然会回头检查自己的左方和上方也就是当前格子所以不会漏掉任何一条边。并查集解法的空间复杂度是 O(m×n)因为要维护 parent 数组和 rank 数组时间上因为路径压缩和按秩合并每次操作的均摊开销接近常数整体还是 O(m×n)。理解并查集解法还有一个额外收获如果题目变成“动态加入陆地每加一块后问当前有多少岛屿”也就是力扣 305 岛屿数量 II并查集就是最优解DFS 和 BFS 反而难以高效处理。2.4 四种实现横向对比对比维度DFS递归DFS手动栈BFS队列并查集时间复杂度O(m×n)O(m×n)O(m×n)O(m×n×α)近似 O(m×n)空间复杂度最坏 O(m×n)最坏 O(m×n)队列最坏 O(m×n)O(m×n)是否修改原数组默认修改默认修改默认修改不修改栈溢出风险高可控无无编码难度低中中偏高我在实际刷题时的一个参考思路是追求简短就用递归 DFS担心爆栈就用 BFS面试官追问“不修改原数组”或“动态加陆地”时再切并查集。三种解法都写一遍这道题才算真正吃透。3. 手写实现完整代码与关键细节分析3.1 DFS 实现Python 与 C 双版本先看 Python 递归 DFS 版本这也是我推荐第一次刷这道题的人先写的版本。def num_islands(grid): if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) count 0 def dfs(i, j): if i 0 or j 0 or i m 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) for i in range(m): for j in range(n): if grid[i][j] 1: count 1 dfs(i, j) return count这段代码有几个细节值得注意。第一if not grid or not grid[0]同时处理了空数组和只有空行的情况顺序不能反否则grid[0]可能越界。第二递归边界条件写在函数最前面一进入就判断简洁且不容易漏。第三把1改成0必须在递归之前完成否则同一个格子会被上下左右四条路径反复访问造成死循环。C 版本结构完全一致只是要注意引用传递否则每次递归都会拷贝整个二维数组class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty() || grid[0].empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } void dfs(vectorvectorchar grid, int i, int j) { if (i 0 || j 0 || i grid.size() || j grid[0].size() || grid[i][j] 0) { return; } grid[i][j] 0; dfs(grid, i 1, j); dfs(grid, i - 1, j); dfs(grid, i, j 1); dfs(grid, i, j - 1); } };两个版本写完建议自己多跑几个测试用例尤其是 1×1、1×n、m×1 这三种极端形状能帮你确认坐标处理和递归终止条件都没有问题。3.2 BFS 实现入队即标记BFS 版本用 Python 写最舒服因为collections.deque的popleft()是 O(1)而如果用 list 的pop(0)是 O(n)大数据量下会慢很多。from collections import deque def num_islands(grid): if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) 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: count 1 grid[i][j] 0 queue deque([(i, j)]) 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 count这里我用了方向数组directions而不是写四段重复的if这是我自己刷到后期才养成的习惯。网格类题目几乎都要处理“四个方向”的遍历把方向抽象成数组之后代码量减少、出错率下降后续遇到“八个方向”“骑士走法”等问题也能复用同一套路。这段代码里最容易踩的坑就是“入队即标记”。注意看第 15 行和第 16 行我在把邻居加入队列之前就执行了grid[nx][ny] 0。如果这两行顺序反了先入队再标记队列中就会出现重复坐标最坏情况下队列会膨胀到远超网格大小性能直接崩掉。3.3 并查集实现编号、合并、计数并查集解法写起来稍长但每一块职责都很清晰。先定义并查集数据结构再写主逻辑class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n self.count 0 def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): 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 def num_islands(grid): if not grid or not grid[0]: return 0 m, n len(grid), len(grid[0]) uf UnionFind(m * n) uf.count sum(line.count(1) for line in grid) for i in range(m): for j in range(n): if grid[i][j] 1: idx i * n j if i 0 and grid[i - 1][j] 1: uf.union(idx, (i - 1) * n j) if j 0 and grid[i][j - 1] 1: uf.union(idx, i * n j - 1) return uf.count这段代码有三个关键点。第一并查集的计数初始值不是 0而是陆地总数因为每个陆地初始都独立成岛合并一次就减少一座岛这比“初始为 0每次发现一块全新疆域再加 1”要直观得多。第二find里用了路径压缩递归地把父节点指向根节点这样后续查找近乎 O(1)。第三主循环里只合并上方和左方原因在 2.3 里说过扫描顺序保证了不会漏边。我最初写并查集时犯过一个错在union里判断rx ry后直接return忘记这时两个节点已经在同一个岛上不应该再减计数。后来我把它想成“只有真正把两棵树合并成一棵树时才需要减一”才彻底纠正过来。3.4 visited 数组与原地修改的取舍三种解法里DFS 和 BFS 默认都修改了grid这是最简单也最推荐的做法。但有些面试场景会明确要求“不能修改输入”或者你需要在一次遍历结束后保留原始网格做后续计算这时就必须引入 visited 数组。用 visited 数组时代码结构几乎不变只是把grid[i][j] 0替换成visited[i][j] True判断条件从grid[nx][ny] 1变成grid[nx][ny] 1 and not visited[nx][ny]。代价是空间复杂度从 O(1)原地修改变成 O(m×n)。我自己的经验是刷题时先问清楚题目允不允许修改原数组如果不确定就按“不修改”来写 visited 版本这样最保险也不会被面试官挑毛病。4. 边界条件与易错点实战踩坑记录4.1 空数组与不规则输入题目给的是标准[[char]]输入但实际刷题时你可能会遇到变种输入是空列表[]或者列表里有一个空列表[[]]。这两种情况如果不处理代码会在grid[0]或len(grid[0])处抛异常。我在 C 里见过更隐蔽的版本vectorvectorchar本身不为空但某些行长度不一样形成“锯齿数组”。虽然力扣测试不会这样但面试官让你手写代码时可以追问一句“假设所有行等长对吧”既展示了你对输入假设的敏感度也规避了后续的边界问题。统一做法是函数第一行就写if not grid or not grid[0]: return 0这个判断同时覆盖了空数组和空行没有多余分支建议背下来形成肌肉记忆。4.2 全 1 大矩阵与递归深度如果输入是一个 1000×1000 的全1矩阵DFS 递归从(0,0)进入后会沿着四个方向一路深入递归深度最坏能达到 100 万级别。Python 默认递归深度上限大约是 1000这种用例下直接报RecursionErrorC 则可能直接栈溢出崩溃。有三种规避方案一是把递归 DFS 改成手动栈用 list 模拟栈二是直接用 BFS 版本队列没有递归深度问题三是用并查集从头到尾不涉及递归调用本身虽然find的路径压缩如果用递归写法也有类似隐患但可以改成迭代写法。我个人的建议是准备面试时把 BFS 作为默认版本记忆因为网格类题目几乎没有不能换 BFS 的。手动栈虽然也能解决爆栈问题但代码里需要自己维护(i, j)坐标栈和入栈前标记两个细节写起来不如 BFS 直觉。4.3 四方向误写为八方向题目明确说“水平方向和竖直方向”也就是只考虑上下左右四个邻居。但很多人在写方向数组时顺手写成了八个方向把对角线格子也当成同一座岛的成员导致原本应该分开的两座岛被误判成一座返回的岛屿数量偏少。我在一次模拟面试里就见过候选人把directions写成directions [(1,0), (-1,0), (0,1), (0,-1), (1,1), (1,-1), (-1,1), (-1,-1)]结果一个由对角线相连的棋盘格图案被算成一块答案直接错了。如果你担心记混可以记一个口诀岛屿讲四邻像素连通才讲八邻。图像处理里的八连通和这里不是一回事千万别混。4.4 BFS 重复入队问题前面提过BFS 里“出队时才标记”会导致重复入队这里展开说一个我实际调试过的例子。假设网格是1 1 1 1从(0,0)开始如果入队时不标记第一次循环会把(0,1)和(1,0)入队第二次循环处理(0,1)时发现(1,1)是1又入队同时它还会再看(0,0)发现已经是0所以不动第三次处理(1,0)时又发现(1,1)是1再次入队。结果(1,1)被加入队列两次虽然最终结果可能碰巧正确但队列长度膨胀而且在更复杂的图形里可能出现死循环。正确写法是“入队即标记”确保每个格子最多进入队列一次。这个教训同样适用于图的最短路径问题BFS 处理节点时永远要在入队时登记访问状态而不是在出队时。5. 复杂度分析与变种题扩展5.1 时间和空间复杂度深挖三种解法的时间复杂度都是 O(m×n)原因相同每个格子最多被访问常数次。DFS 和 BFS 中一个格子一旦被改成0就再也不会被当作处理对象外层主循环还会把每个格子看一遍所以总共是遍历一遍加每座岛内部访问一遍合起来还是 O(m×n)。并查集则是在每个1格子上做常数次find/union均摊下来也接近 O(m×n)。空间复杂度上三种解法有区别。DFS 递归版的空间主要消耗在调用栈上全1矩阵最坏深度为 m×n所以空间 O(m×n)。BFS 的空间是队列的最大长度在窄长矩阵如 1×n 时队列只有常数长度在满矩阵时最坏也能到 O(m×n)所以通常说“最坏 O(m×n)可近似记为 O(min(m,n))”。并查集固定需要 parent 和 rank 两个长度为 m×n 的数组空间 O(m×n)。这里有个常见的面试追问“你刚才说 BFS 空间是 O(min(m,n))能不能解释一下”这个问题其实考察你对队列在网格上扩散规律的理解。BFS 在网格里是按“层”扩散的某一时刻队列中存放的是当前层和下一层的所有节点而层的最宽处受限于矩阵的短边所以可以写成 O(min(m,n))。面试时能把这个道理讲清楚比公式背得熟更有说服力。5.2 变种题最大面积、周长、被围绕的区域吃透这题之后直接受益的是下面几个高频变种。695 岛屿的最大面积DFS 不再只计数而是让每个 DFS 返回它遍历过的格子数主循环里用 max 更新。核心逻辑和这题一模一样只多一个返回值。463 岛屿的周长每个1格子本身贡献 4 条边但每和相邻陆地在某个方向共享一条边总周长就减 2。也可以 DFS 时遇到边界或水就加 1遇到已访问格子就跳过。两种写法都能过后者和本文章的 DFS 结构更接近。130 被围绕的区域反向思维先找边界上的O从边界出发把所有能连到的O标记成特殊字符比如#然后全图扫描把剩余的O改成X最后把#改回O。这个“先逆向标记再统一处理”的思路和岛屿数量里的“先淹岛再数数”异曲同工。1254 统计封闭岛屿的数量先把边界上能到达的所有0区域“淹没”再对内部的0块数连通分量数出来的就是被1包围的封闭岛屿。我的建议是刷完这题按顺序把 695、463、130 三题各写一遍你会发现自己对“方向数组 状态标记 连通分量”这套组合拳已经形成肌肉记忆。5.3 进阶思路动态岛屿与沉没法思想力扣 305 岛屿数量 II 是这题的动态版本网格初始全是水每次操作在指定位置把水变成陆地问每次操作后有多少岛屿。DFS 和 BFS 每次都要重新扫描全图复杂度直接爆炸并查集则天然支持这种增量操作。每次新增一块陆地时就把它和四周的1邻居合并计数器加 1 减去成功合并次数即可得到新的岛屿数量。还有一个思想值得单独提出来这道题里的“把陆地改成水”其实是经典的“沉没法”。你想象一个岛屿浮在水面上你每找到一座岛就让它沉下去那么扫完之后所有岛屿都被沉没了计数也完成了。这个思想在二维网格连通类问题里非常好用很多题解里提到的“flood fill”算法就是它。理解了这个比喻你就能明白为什么可以原地修改网格也就能在面试时把这个“为什么这样不会影响后续遍历”解释得特别生动。6. 面试表达与现场调试技巧6.1 从题意到口述思路的引导顺序面试中拿到这道题不要上来就写代码。我推荐的表达顺序是先和面试官确认输入类型和边界再快速建模把“网格是图、岛屿是连通分量”这句话说出来然后给出你最顺手的一种解法。例如可以这样说“我先把网格抽象成图每个格子是一个节点上下左右是边那么岛屿就是由字符1构成的连通分量。我可以遍历每个格子遇到一个1就把计数加一然后通过 DFS 把这个连通分量里的所有1都改成0这样后续就不会重复计数。时间复杂度 O(m×n)空间上递归最深可能 O(m×n)。如果担心大矩阵爆栈我可以换成 BFS 用队列实现同样逻辑。”这样一段话既展示了图形建模能力又主动交代了复杂度和潜在风险还给出了备选方案。面试官大概率会点点头让你直接写 BFS 版本。6.2 口头分析复杂度的正确姿势口头分析复杂度时有个常见误区只说“O(m×n)”就停了。再往深说一层面试官的印象会好很多。对于 DFS你可以说“每个格子最多被修改一次外层循环每个格子也最多检查一次所以时间是 O(m×n)。空间上最坏情况是整张图全是陆地递归深度达到 m×n所以空间也是 O(m×n)。”对于 BFS你补上一句“队列里某一时刻最多存的是 BFS 的某一层的节点在网格类问题里可以记为 O(min(m,n))最坏不超过 O(m×n)。”对于并查集你加一句“并查集两个数组的长度都是 m×n空间 O(m×n)由于路径压缩和按秩合并均摊时间接近常数整体 O(m×n)。”能把话说得这么细说明你是真的理解而不是背答案。6.3 手写代码时的顺序建议手写代码时我建议按下面这个顺序来能有效减少划线涂改先写空输入判断。这一行几乎不会错放在最前面能帮你预热。定义 m、n、计数器和方向数组。写主循环遇到1计数加一然后调用辅助函数。最后写辅助函数也就是 DFS 或 BFS 的核心。有一个小技巧如果你在写 BFS先把grid[nx][ny] 0写在queue.append之前从一开始就养成正确的标记习惯。如果你写 DFS把越界和访问判断合并到一行像if i 0 or ... or grid[i][j] 0: return可以减少一个嵌套层级。写完后至少跑三个测试用例一个 1×1 全陆地、一个多行多列含多个岛、一个全是水的矩阵。这三个用例能覆盖绝大多数低级错误跑完再主动说“我测一下空数组”面试官通常就不会再挑边界条件的刺了。6.4 分享一个我在调试时常用的方法如果代码跑出来结果不对而你又看不出哪里有问题有一个很笨但很有效的方法在每次把1改成0的地方打印当前坐标和整个网格状态。我自己第一次刷这题时就是靠这个方法发现了一个微妙的 bug我把行列坐标写反了grid[x][y]写成了grid[y][x]导致在非方阵上索引越界而结果错误。这类坐标错位在方阵上不会暴露只有跑3×5这种非方阵用例时才看得出来。所以我的建议是写完代码后刻意用一个行数和列数不一样的测试用例验证一遍比如grid [[1,0,1,0,1]]这能快速暴露m和n用反的问题。最后再分享一点个人体会。我刷这题第一遍时递归 DFS 写得磕磕绊绊直到某天突然想通“把访问过的陆地改水”这个操作本身就是在做连通分量标记之后遇到 flood fill 类题目全都会写了。第二遍刷是因为有次线上笔试遇到全1大矩阵导致递归爆栈才老老实实把 BFS 版本背了下来。第三遍是准备系统设计类面试时顺手复习并查集发现这题是教科书级例题。如果你也在准备面试我认真建议把这题的三种解法都各写一遍再顺手把 695、463、130 三题刷掉之后再看任何“二维网格 连通块”的组合题都会觉得格外轻松。