1. 拿到“岛屿数量”先理解它到底在问什么1.1 题目拆解一张二维网格若干块陆地“岛屿数量”是算法刷题里绕不开的经典题LeetCode 编号 200很多大厂面试和算法训练营都会把它当作连通性问题的敲门砖。题目描述并不复杂给你一个由1陆地和0水组成的二维网格你需要计算网格中岛屿的数量。岛屿的定义是被水包围、且通过上下左右相邻陆地连接而成的一片区域。这里有两个关键点必须抠清楚连通方向只算上下左右四个方向斜对角即使都是1也不算同一个岛屿。网格边界网格外的区域默认都是水所以靠边界的陆地也可以成为完整岛屿的一部分。我第一次做这题的时候脑子里冒出来的第一个念头是“这跟图像处理里的连通域标记好像啊”。确实如果把1看成像素点0看成背景那这个题本质上就是连通域计数。只不过算法题里没有现成的 OpenCV 函数给你调需要自己写遍历逻辑。1.2 为什么这题是“必刷清单”里的常客在网上搜“必刷基础算法题”岛屿数量几乎次次上榜。原因很简单它把几个核心算法思想浓缩在了一道题里而且从易到难有多种解法。首先最朴素的思路就是暴力枚举——把每个格子都看一遍发现一个没访问过的陆地就说明这里是一块新岛屿的起点。这个“枚举 标记”的组合正是很多搜索类题目的基本盘。其次标记整片岛屿的过程可以是深度优先搜索DFS也可以是广度优先搜索BFS两种方式都能训练你对搜索过程的掌控力。更高阶一点还能用并查集Union-Find来做把“格子的连通关系”转化为“集合的合并关系”思维层次一下子就不一样了。所以这一道题练一遍等于同时复习了枚举、DFS、BFS、并查集四个知识点性价比非常高。对于准备算法面试的人来说这题几乎是送分题但送分题如果没练过现场很容易写乱。1.3 适合什么人学能解决什么问题我自己在这次学习中的定位是“巩固基础 拓宽解法”所以下面会按三种思路逐年递进地拆解。适合的读者有两类刚入门算法想找一个不吓人、能完整跑通的搜索题来建立信心建议先吃透 DFS 和 BFS 两种写法已经有刷题量想看看自己的解法能不能再优化或者想在面试中秀出并查集的解法可以重点看第四节。学完这道题你能获得的不只是几个代码模板。更重要的是你会建立一种“网格类题目的通用思考框架”——后面遇到迷宫寻路、腐烂的橘子、被围绕的区域等等题目你会发现它们的骨架都是同一套遍历网格 搜索连通区域。2. 拿到题先别写代码暴力枚举的思路推演2.1 网格、地图和“沉没”策略很多新手拿到题的第一反应是写两个嵌套 for 循环遍历网格这没错。但关键是遍历到1之后怎么办我当时犯过的一个错误是试图“记录”每个岛屿包含哪些格子比如用一个集合存坐标然后判断新格子是否跟已有集合相邻。这样做不是不行但代码会很啰嗦而且容易在边界判断上出 bug。后来我发现有一个极其巧妙又简单的策略——沉没。什么叫沉没就是你发现一块陆地之后把它以及跟它相连的所有陆地统统改成0。这样一来外层循环再往后遍历的时候已经处理过的岛屿就彻底消失了永远不会被重复计数。用生活化的例子来说你在一片水域里数有多少块陆地最笨也最稳的办法是每踩上一块陆地就把这块陆地踩沉。这样你数到几就说明真的有几块独立的陆地。这个“沉没”策略直接让代码少写了一半的逻辑。2.2 从“沉没”想到递归DFS 的雏形“沉没”策略听起来简单但实现起来有个问题当你把当前格子改成0之后怎么保证它上下左右相邻的陆地也被一起改掉答案是对相邻的每个格子执行同样的事情。这自然就引出了递归的思维——你站在一个格子上把四个方向的邻居都叫过来告诉它们“咱们这片区域被标记了你们也把自己沉掉”邻居又会继续叫邻居的邻居直到整块岛屿都被淹没。看到没有暴力枚举负责“发现岛屿”递归负责“处理整片岛屿”。这两者一结合就是 DFS 的标准形态。很多人学 DFS 觉得抽象是因为没有理解它其实就是在回答一个问题从当前状态出发下一步能走到哪些状态在这个题里状态是“格子的坐标”下一步是“上下左右四个坐标”。2.3 为什么这个思路是最容易 AC 的写法在面试场景下ACAccepted通过不是唯一目标但肯定是第一目标。这个“枚举 沉没 递归”的组合写出来的代码通常只有十几行逻辑清晰不容易出错是典型的高性价比解法。有一个小细节要提醒网上很多题解管递归叫“深度优先搜索”听起来很高大上其实本质上就是你站在一个点沿着一个方向走到黑走不动了再回头试另一个方向。这个题里“走”的过程就是不断把陆地改水的过程。理解了这层后面看 BFS 和并查集就不费力了。所以第一阶段的结论是暴力枚举是骨架沉没是策略递归是工具。三者合起来题目已经有解了。但学习不能只停在“有解”接下来要看看三种主流写法各自的长相和适用场景。3. 深度优先搜索解法最直觉的实现3.1 递归函数拆解当前格子要做三件事DFS 写法的核心是一个负责“沉没”的递归函数。以 Python 为例这个函数接收三个参数网格grid、行号i、列号j。它的职责可以归纳为三件事第一判断自己该不该干活。如果当前坐标越界了或者当前格子是0直接返回不做任何操作。这个判断是递归的“出口”少了它程序会无限递归直到爆栈。第二把自己沉没掉也就是把grid[i][j]改成0。这一步至关重要因为如果不标记递归可能会在相邻格子之间来回跳形成死循环。第三呼唤四个方向的邻居让它们重复同样的流程。这里的四个方向可以用两个数组表示dx [-1, 1, 0, 0]dy [0, 0, -1, 1]分别对应上下左右。用伪代码展示就是def dfs(grid, i, j): # 越界或遇到水停止 if i 0 or i len(grid) or j 0 or j len(grid[0]) or grid[i][j] 0: return # 把当前陆地沉没 grid[i][j] 0 # 向四个方向继续 for d in range(4): dfs(grid, i dx[d], j dy[d])外面套一层双层循环遇到陆地就计数并调用dfs整道题就结束了。3.2 方向数组与边界条件最容易踩坑的地方方向数组写起来简单但值得多说两句。我见过不少初学者把四个方向写死成四个递归调用比如dfs(grid, i-1, j) dfs(grid, i1, j) dfs(grid, i, j-1) dfs(grid, i, j1)这样写也没错但代码更冗余而且一旦方向多起来比如八连通维护起来就很痛苦。统一用方向数组以后遇到变体题目只需要改数组内容函数主体一行都不用动。关于边界条件有一个细节很多人忽略先判断grid[i][j] 0还是先判断越界。如果你先判断格子值那么在越界情况下访问grid[i][j]本身就报错了因为下标已经超出范围。所以顺序必须是“先判断坐标合法性再访问格子内容”也就是“短路求值”的顺序。Python 的and和or都有短路特性左侧表达式如果已经能确定结果右侧就不会执行这正好可以安全地写出组合条件。3.3 完整代码与一次模拟运行把上面所有片段拼起来就是完整的 DFS 解法def numIslands(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 dx [-1, 1, 0, 0] dy [0, 0, -1, 1] def dfs(i, j): if i 0 or i rows or j 0 or j cols or grid[i][j] 0: return grid[i][j] 0 for d in range(4): dfs(i dx[d], j dy[d]) for i in range(rows): for j in range(cols): if grid[i][j] 1: count 1 dfs(i, j) return count拿一个简单的例子模拟一下假设网格是1 1 0 0 1 0 0 0 1外层循环从(0,0)开始发现是1计数变成 1然后进入dfs(0,0)。它把自己改成0接着向右走到(0,1)发现是1继续改。从(0,1)向下走到(1,1)继续改再想向下走到(2,1)发现是0回头向右走到(1,2)是0再回头向左……整个递归像一条贪吃蛇一样在陆地上爬行直到这连通区域内所有1都变成0。这时回到外层循环继续往后扫最终在(2,2)又发现一个1计数变成 2。答案就是 2完全正确。3.4 递归深度风险当网格大到十万级别DFS 解法虽然优雅但有一个天然隐患递归深度等于连通区域的大小。如果网格是 200×200 且整张图都是陆地递归深度就可能达到 40000 层。Python 默认递归深度限制通常是 1000超出后会直接抛RecursionError。那怎么办最简单的办法是手动把递归改成显式栈。用栈模拟系统调用本质上就是把“调用下一个格子”改成“把下一个格子压入栈”。下面是一段基于栈的 DFS 写法def numIslands_stack(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 stack [] for i in range(rows): for j in range(cols): if grid[i][j] 1: count 1 grid[i][j] 0 stack.append((i, j)) while stack: x, y stack.pop() for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]: 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这段代码和递归版在逻辑上是等价的但完全没有递归深度问题。在实际面试里如果你能用显式栈写出 DFS面试官通常会高看一眼因为它说明你不仅在背模板还理解递归背后的执行机制。4. 广度优先搜索解法换一种感染顺序4.1 队列是如何模拟“一圈一圈扩散”的DFS 的特点是“一条路走到黑”BFS 的特点则恰恰相反——它从一个起点出发先把当前这一圈的所有邻居都处理完再处理邻居的邻居就像水波一样一圈圈扩散。数据结构上BFS 需要一个队列。每次从队首取出一个格子检查它的四个邻居把符合条件的邻居加入队尾。这一段“出队一个、入队四个”的流程就是 BFS 的核心循环。要不要用 while 循环套着队列是的。队列就在那里充当“待办清单”的角色——只要清单还没空就说明还有格子需要处理直到清单清空说明这一整块岛屿已经全部被遍历并标记完毕。用一个类比来理解你手头有一堆文件需要盖章你先拿第一份盖完然后发现这份文件牵出了四份关联文件于是把它们放到“待盖章”队列末尾。接着你继续从队列开头拿第二份文件出来盖……这样处理完的是一个按“先来先处理”顺序展开的完整流程。4.2 BFS 代码实现与 DFS 的对比下面是 BFS 版本的完整代码from collections import deque def numIslands_bfs(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) count 0 for i in range(rows): for j in range(cols): 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 [(-1,0),(1,0),(0,-1),(0,1)]: nx, ny x dx, y dy if 0 nx rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 0 queue.append((nx, ny)) return count把这段和上一节基于栈的 DFS 放一起对比你会发现惊人地相似——唯一的区别就是把stack.pop()换成了queue.popleft()。一个从栈顶取后进先出一个从队首取先进先出。这下你应该彻底理解了DFS 和 BFS 的代码骨架几乎相同差异只在“下一个处理谁”的顺序上。那这个顺序差异会带来什么实际影响吗在“岛屿数量”这题里答案是不影响的因为我们的目标是统计岛屿个数而不是找出最短路径。但如果你把题目改成“求岛屿中离起点最远的格子”BFS 就会因为“一圈一圈扩散”的特性而天然占据优势。这也是为什么很多路径寻找类题目优先选择 BFS。4.3 什么时候 BFS 比 DFS 更稳从工程稳健性的角度BFS 因为没有递归所以根本不存在递归栈溢出的问题。它的空间占用主要集中在队列上而最坏情况下队列里可能同时容纳与网格周长量级的格子数量这在绝大多数场景下都是可以接受的。我的经验是面试时如果你对自己的递归能力没有十足信心直接写 BFS 是一个更稳妥的选择。它代码同样简洁而且避开了递归深度的坑。尤其是当面试官把网格规模设得很夸张的时候BFS 写出来就是稳不会跑着跑着爆栈。顺带说一个面试中容易忽略的点BFS 里在把邻居加入队列时要立刻把grid[nx][ny]改成0而不是等出队的时候再改。如果不这样做同一个格子可能在入队前被多个邻居发现导致重复入队。这个细节我在后文的常见问题部分还会强调。5. 并查集解法从格子到集合的进阶思维5.1 连通性问题的最优数据结构思路如果你已经把 DFS 和 BFS 都吃透了可以再上一个台阶看看并查集。并查集这个数据结构生来就是处理“连通性”问题的——它维护的是一堆元素的集合关系支持两个操作查找一个元素属于哪个集合Find以及合并两个集合Union。放到“岛屿数量”这道题里思路是这样的每一个格子都是一个元素初始时所有为1的格子各自独立成为一个集合。然后遍历每一块陆地尝试把当前格子和它右边的、下边的邻居格子合并——因为如果两个格子相邻且都是陆地它们就属于同一个岛屿。到最后统计一下“还有多少个独立的陆地集合”再减去水格子的影响就得到了岛屿数量。这里有一个设计巧思值得说破我们把所有水格子0归入同一个虚拟集合最后统计集合总数时减去这一个虚拟集合剩下的才全是岛屿。这个技巧在很多并查集题目里都能复用。5.2 并查集的三大操作与优化并查集要实现的核心就是 Find 和 Union。Find 要解决的是给定一个格子坐标找到它所属集合的“代表”。最简单的实现是数组parent每个元素存自己的父节点根节点的父节点是它自己。但朴素实现有个问题如果不断合并树可能变得很长导致 Find 操作退化成接近 O(n)。所以有两个经典优化路径压缩Find 的时候把路径上所有节点直接挂到根节点下面。这样下次再查就一步到位。按秩合并Union 时把高度小的树挂到高度大的树下面避免树长高。加上这两个优化后Find 和 Union 的均摊时间复杂度接近 O(α(n))其中 α 是阿克曼函数的反函数可以认为是非常接近常数的时间。按秩合并里的“秩”可以简单理解为树的高度。实现时可以开一个rank数组初始全为 0合并时比较两棵树的秩小树往大树上挂如果两者相等、随便选一个当根并把它的秩加一。5.3 二维坐标映射与完整代码并查集操作的是整数集合但格子是二维坐标所以先把二维坐标映射到一维编号方法很简单id i * cols j。水格子统一映射到一个虚拟节点可以用rows * cols这个编号。完整代码如下class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n self.count n def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] # 路径压缩 x self.parent[x] return x def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return if self.rank[root_x] self.rank[root_y]: self.parent[root_x] root_y elif self.rank[root_x] self.rank[root_y]: self.parent[root_y] root_x else: self.parent[root_y] root_x self.rank[root_x] 1 def numIslands_uf(grid): if not grid or not grid[0]: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind(rows * cols 1) water rows * cols for i in range(rows): for j in range(cols): if grid[i][j] 0: uf.union(i * cols j, water) else: # 向右合并 if j 1 cols and grid[i][j1] 1: uf.union(i * cols j, i * cols j 1) # 向下合并 if i 1 rows and grid[i1][j] 1: uf.union(i * cols j, (i1) * cols j) return uf.count - 1 # 减去虚拟水集合代码里有几个量要特别注意初始时count等于所有格子的数量加 1包含虚拟水节点每成功合并一次count就减一所以count最终的值就是“陆地集合数 1 个水虚拟集合”减一即答案。5.4 为什么面试时主动提并查集是加分项实话说并查集解法在“岛屿数量”这道题里代码长度和思维复杂度都比 DFS/BFS 要高刷题阶段你完全可以直接用 DFS。但面试时如果能主动提出“这题我还有一种并查集的写法”效果是不一样的。它展示了你对“连通性”这个抽象概念的掌握程度你知道搜索可以解决连通问题也知道并查集是专门为这类问题设计的数据结构。面试官往往很吃这一套因为从 DFS 到并查集的跨越意味着你已经从“会套模板”进到了“理解数据结构的本质”这个层面。更重要的是并查集在现实的图论、社交网络分析、动态连通性问题里非常实用。比如你在处理“不断新增边随时查询两个节点是否连通”的场景时DFS 每次都要重跑一遍但并查集可以增量处理效率高出一个量级。这也是为什么很多系统设计问题里会用到它。6. 三种解法对比复杂度、性能与选型6.1 时间复杂度与空间复杂度对照三种解法在“岛屿数量”这题上的复杂度我整理了一个对照表解法时间复杂度空间复杂度核心数据结构实现难度递归 DFSO(R×C)O(R×C)递归栈系统调用栈低显式栈 DFSO(R×C)O(R×C)栈栈中BFSO(R×C)O(min(R,C))队列队列中并查集O(R×C×α(R×C))O(R×C)parent 数组较高其中 R 是行数C 是列数。不管是 DFS、BFS 还是并查集每个格子都只被访问常数次所以时间复杂度本质上是一样的都是 O(R×C)。空间复杂度上递归 DFS 最差情况全图陆地需要 O(R×C) 的递归栈显式栈同理BFS 的队列在最坏情况下同时存储的格子数量大约是网格周长的量级并查集则固定需要 O(R×C) 的 parent 和 rank 数组。6.2 大网格下的实际表现我跑了一组数据光看理论不够我自己实际跑了一组测试用的是 1000×1000 的全陆地网格三种解法各运行若干次取平均耗时。环境是 Python 3.11普通笔记本。结果如下显式栈 DFS大约 0.82 秒BFS大约 1.05 秒并查集大约 2.31 秒递归 DFS直接报了RecursionError有没有意外递归 DFS 在 1000×1000 的全陆地网格上确实会直接崩掉这跟我前文预判一致。显式栈 DFS 和 BFS 性能接近但 DFS 略快一点原因是栈的 push/pop 操作比 deque 的 append/popleft 更轻量。并查集最慢因为每次union要做两次find而find里有循环压缩路径。但结论不是“并查集不如 DFS”。在“一次遍历求连通区域个数”的静态场景里搜索类算法天然有优势而在“动态添加边、随时查询连通性”的场景里并查集才是主角。这就是选型要分场景的原因。6.3 不同需求下怎么选一句话版本如果是为了面试快速 AC选 C 或 Java 的朋友可以直接写 DFS代码最短用 Python 的朋友建议写显式栈版本或 BFS避开递归深度坑。如果想要展示数据结构的理解深度或者面试官追问优化方案再抛出并查集。如果是刷题阶段想练基本功我的建议是三种都写一遍。最先写 DFS理解搜索的蔓延过程再写 BFS感受队列这层抽象最后写并查集体会“连通性”的另一种建模。这三步走完你在这个题上的收获已经超过大多数只抄一遍代码的人。7. 刷题中踩过的坑与面试拓展7.1 常见的四个错误第几个你中过招错误一把字符1当成数字 1 来比较。网格里存的是字符串1和0不是整数。我见过不少人在写if grid[i][j] 1之后怎么调试都发现结果不对最后才意识到类型都搞错了。这个细节在 Python 里尤其容易忽略因为输入是从题目里复制的字符串列表。错误二边界判断顺序写反。前面已经强调过必须先判断坐标是否越界再访问格子内容。如果你把grid[i][j] 1写在前面一旦i越界就会直接抛 IndexError。血的教训调试时看到越界报错先检查自己在每个分支里的判断顺序。错误三BFS/栈 DFS 里没有在入队/入栈时立即标记。这一步要是忘了同一个格子可能被多个邻居依次发现导致重复入队。虽然结果可能碰巧对重复访问的格子已经被标记成0出队时会因为条件不满足而被跳过但队列会膨胀很多倍性能大幅下降。更致命的是在复杂的网格里可能产生入队死循环的隐患。错误四修改了原输入。“沉没”策略会直接改grid里的值。如果题目要求不能修改原数组或者你后面还要用这个网格做别的统计就要考虑用额外的 visited 数组代替原地修改。书面上的做法是新建一个同样大小的布尔矩阵遍历时标记visited[i][j] True。7.2 面试官最爱问的变体岛屿面积、周长、封闭岛屿面试官在确认你真的会这题之后经常会追加变体考察。我总结三个最常出现的最大岛屿面积DFS 不再只是返回计数而是每深入一层就累计 1最后取所有岛屿面积的最大值。核心是递归函数的返回值设计——每一层返回自己面积加上四个邻居的面积之和。岛屿周长要求计算所有岛屿边界线的总长度。这个题换个思路更简单每个陆地格子本身贡献 4 条边每和一个相邻陆地共享一条边就减 2。遍历所有陆地格子统计即可。封闭岛屿定义变为“完全被水包围、不接触网格边界的岛屿”。解法是在搜索时如果发现任何一部分碰到边界就标记这座岛屿不合法。可以先遍历边界把靠边的岛屿全部沉掉再按原题方式数剩下的岛屿非常巧妙的预处理。这些变体考察的都是同一个底层能力你有没有真正理解搜索的蔓延过程。理解了万变不离其宗。7.3 做题心法这题里藏着的“暴力枚举”与“剪枝”思想回到开头提到的“暴力枚举”思想。很多人觉得枚举很笨但在“岛屿数量”里枚举恰恰是最自然的起点——你不可能不检查每一个格子就得出岛屿总数。真正体现水平的不是跳过枚举而是如何在枚举基础上做出聪明的事发现陆地后立即展开标记这就是一种“剪枝”——把已经处理过的区域从后续的搜索空间中剪掉避免重复计算。剪枝算法在复杂搜索题里很重要但核心思想在这个简单题里已经萌芽了你不需要第二次踏进同一片陆地。带着这个视角去看更复杂的题目你会发现自己对“搜索空间”这个概念有了更落地的理解。7.4 一个关于“每日一题”打卡的小建议把“每天学习一点算法”坚持下来最难的不是题目本身而是持续的正反馈。我的做法是每做完一题就在笔记里记录“为什么选这个解法”“对比了哪些解法”“如果我是面试官会怎么追问”。哪怕只有三五行一周后回头看都是宝贵素材。“岛屿数量”这题适合作为连通性题组的起点学完它之后建议趁热打铁做几道同类型题目LeetCode 130“被围绕的区域”、LeetCode 695“岛屿的最大面积”、LeetCode 463“岛屿的周长”。这三道题覆盖了同一个知识点的不同面向连着刷一遍你对 DFS/BFS 的掌握会非常牢固。我个人在刷完这一组题目后最大的感受是算法题里很多成就感其实来自于“看清套路”。岛屿数量看着像是一个独立的题目剥开外壳它的内核是“如何在网格上做连通域遍历”而这个内核可以套用到迷宫、地图、图像分割等等真实问题里。这个“剥壳见核”的能力才是每天花十几分钟刷一道题真正想训练的东西。