聊到“孤岛”很多人脑子里蹦出来的第一个画面可能不是算法题而是某款游戏里的热带岛屿或者是各种生存综艺里的无人小岛。但在图论刷题圈里“孤岛”是一个再具体不过的题型给定一张二维网格1代表陆地、0代表水域那些完全被水包围并且不触碰网格边界的陆地连通块才叫孤岛。这是我刷图论专题第38天碰到的核心题目也是从“会写DFS”到“真正理解连通性”之间的一道分水岭。这篇文章就把我那天整理的东西完整摊开孤岛的定义为什么容易搞混、和普通岛屿计数题差在哪、三种主流解法各自怎么写、提交代码时反复踩的坑以及从这道“基础题”能延伸出去的面试变形。不管你是刚开始刷图论的新手还是想快速过一遍DFS/BFS/并查集在网格题里的应用这篇都值得花十分钟看完。1. 别把图论里的孤岛和游戏里的孤岛混为一谈问题定义与本质1.1 一段简单的输入样例藏着一个容易理解偏的概念先看一个最经典的网格示例1 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0这个图里肉眼扫一遍能看到好几块陆地。但如果问“这里面有多少个孤岛”很多第一次接触的人会凭感觉回答左上角那块算一个中间那块算一个右边那块也算一个。这个回答恰恰是错的。图论中的孤岛有一个硬性前提整个陆地连通块必须完全被水包围并且不能和网格边界有任何接触。只要连通块里有一个格子落在第一行、最后一行、第一列或者最后一列这个连通块立刻失去“孤岛”资格。所以上面这个例子里左边那块陆地连着第一行和第一列出局中间那块陆地直达第三列和最后一行出局只有右下角那个孤零零的1才是唯一的真孤岛。换句话说判断孤岛的关键不是“它周围有没有水”而是“它有没有偷偷摸摸伸一条腿到地图边缘”。1.2 孤岛和普通岛屿数量题的本质区别很多刷题指南把“孤岛”当成“岛屿数量”的一个小变种这个说法方向没错但如果只把它当成小变种去刷会漏掉一个关键的思维升级点普通的岛屿数量题重心在“找到每个连通块并计数”孤岛题重心在“判断连通块与边界的关系”。这两个重心导致解法路径完全不同。普通岛屿数量题你可以从任意一个未被访问过的1出发DFS/BFS把整个连通块打上标记计数器加一。因为题目不关心这个连通块在哪只关心有几个。孤岛题如果也这么做你会发现一个问题你确实把每个连通块都找出来了可你怎么知道某个连通块是否连到边界你得额外记录这次遍历过程中有没有碰到边界格子。这当然也能做但代码写起来别扭而且容易在“记录”这一步出错。更干净的做法是完全反过来先把所有和边界相连的陆地连通块全部标记成“非孤岛”剩下的陆地自然就是孤岛。这种“先把干扰项排除掉再统计答案”的思路就是孤岛题真正的考点。1.3 一个定义衍生出的多个问法孤岛的定义本身很简单但不同题目会把同一个定义包装成不同的问法。最基础的是问数量网格里有多少个孤岛。再进阶一点是问面积所有孤岛的陆地格子总数是多少LeetCode 1020“飞地的数量”其实就是这个问法。还有一种常见变体叫“填充孤岛”或者“淹没孤岛”把网格里所有孤岛改成水域只保留贴着边界的陆地。这个变体也经常出现在企业笔试里本质上考察的还是同一套“边界连通块判定”能力。所以不要觉得“孤岛基础”只对应一道题它是一整类网格连通性问题的地基。把这个地基打牢后面遇到什么“被围绕的区域”“飞地数量”“填海造陆”都能快速迁移。2. 边界接触的判定是唯一核心为什么直觉在这里不靠谱2.1 “看起来被围住”不等于“真的是孤岛”人类看图有一个很自然的直觉只要一块陆地周围是水它就是孤立的。但在网格题里这个直觉经常坑人。举个例子0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 0 0 0 0 0 0这块陆地虽然没有直接贴到第一行或最后一行但它也没有贴到第一列或最后一列看起来就是一块标准的孤岛。可是如果有一块陆地通过一条宽度为1的“走廊”悄悄连到边界比如1 1 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 1 0左边这块陆地有一条纵向的通道一路通到第一行。这种“通道型”连通块特别容易在视觉上被忽略因为通道很细你扫一眼会觉得那是两块分开的陆地但DFS一跑就会发现它们属于同一个连通块并且这个连通块接触了边界所以它不是孤岛。2.2 判断步骤拆解开只有一句话把题意抽象成算法步骤其实只有三步遍历网格的四条边界找到一个陆地格子就启动DFS/BFS。从这个格子出发把整个和它连通的陆地连通块全部标记为“已访问”或者直接改成水域如果你不关心原数据。遍历整个网格剩下的没有被访问过的陆地格子都属于孤岛。为什么边界遍历能解决所有判断问题因为一个连通块只要接触边界它的所有格子之间是联通的从边界上那个入口出发必然能走遍整个连通块。如果你把边界上所有连通块都标记完了剩下的陆地连通块就绝对不碰边界自然满足孤岛的定义。这个反证逻辑非常干净如果一个陆地连通块接触边界那它一定在边界遍历时被访问到如果一个连通块在边界遍历后仍然是未访问状态那它不可能接触边界。2.3 什么时候用“标记”什么时候用“直接改成水”我在看各种题解时发现不同写法对“处理边界连通块”有两种处理方式。一种是把边界连通块标记为 true已访问最后统计未访问的陆地。这种做法的好处是不会破坏原网格数据适合后面还要用原数据的场景。另一种是直接把边界连通块改成 0水最后统计还剩多少个 1。这种做法代码更短但会修改原始输入如果面试官问“你能不能再写个函数复用”可能会有点尴尬。我个人建议初学阶段用第一种“额外标记”的方式因为思路更显式不容易把自己绕晕。等你写熟了再根据自己的习惯选择要不要省掉 visited 数组。3. 三种主流解法对比DFS、BFS 与并查集各自适合什么场景3.1 DFS代码最短但要注意递归深度DFS 是绝大多数人写网格连通题的第一选择因为它和“递归”绑定得很自然从某个格子出发向上下左右四个方向递归遇到越界、水域、已访问就回头。孤岛题用 DFS 的写法也很直接先从四条边界的陆地格子分别启动 DFS把边界连通块全部标记。再遍历整个网格遇到没访问过的陆地格子就计数并标记整个连通块。DFS 的优点是代码短、结构清楚适合快速解题和面试时展示思路。缺点是递归深度受系统栈限制如果网格是 500×500 甚至 1000×1000 且全是陆地递归深度可能冲上几千层某些平台上会爆栈。这时候要么手动把递归改成栈要么换 BFS。3.2 BFS用队列模拟扩散天然不怕深递归BFS 的思路完全一致只是把递归换成了队列。从边界陆地格子出发把相邻陆地压进队列一层层向外扩散直到队列为空。BFS 的优点是迭代实现没有递归栈溢出风险配合 visited 数组一起用很稳定。缺点是代码比 DFS 稍长一点需要自己维护队列而且如果你不熟悉queue的用法可能觉得不如递归来得顺手。刷题的时候我一般默认写 DFS但一旦发现题目没有明确限制矩阵大小或者矩阵可能很大我会主动切到 BFS 求稳。面试时也可以跟面试官提一句“我担心递归深度所以用 BFS 实现”这种小细节会被视作工程意识。3.3 并查集一种“找爹”的另类解法适合批量连通性查询并查集Union-Find在孤岛题里属于偏进阶的写法但理解了之后会觉得很有意思。核心思路是把所有陆地格子看成一个个节点相邻的陆地合并到同一个集合。同时设置一个虚拟的“边界节点”把所有接触边界的陆地格子都合并到这个虚拟节点下面。最后遍历所有陆地格子凡是和虚拟边界节点不在同一个集合里的就是孤岛。并查集的优势在于如果你需要多次查询“某块陆地是不是孤岛”并查集可以在预处理后给出 O(α(n)) 级别的判断。这在一次遍历题里体现不出太大优势适合那些“多次询问、动态修改”的进阶题。但代价也很明显代码量大一维数组下标转换容易出错而且对新手来说“虚拟节点”这个抽象概念需要适应。所以我的建议是面试时优先 DFS/BFS并查集作为额外加分项提出来就好。3.4 横向对比怎么选解法时间复杂度空间复杂度代码量风险点推荐场景DFSO(m×n)O(m×n)递归栈短大矩阵可能爆栈面试快速答题、小矩阵BFSO(m×n)O(m×n)队列中无递归风险大矩阵、生产级稳妥写法并查集O(m×n×α)O(m×n)较长下标转换容易错需要多次查询连通性的场景三者时间复杂度都是 O(m×n)因为你至少要把每个格子访问一遍。空间上如果直接在原数组上标记可以省掉 visited 数组但我不建议为了省这一点空间放弃清晰度。4. 手写完整代码与模拟以C为例从边界“污染”整个标记流程4.1 一套干净可复用的C实现下面这套代码我当天调试完就觉得值得存进自己的代码库因为它把“边界遍历”和“孤岛统计”拆成了两个独立函数逻辑清晰后面做变形题时改起来也方便。#include vector #include queue using namespace std; class Solution { public: int numOfIslands(vectorvectorint grid) { if (grid.empty() || grid[0].empty()) return 0; int m grid.size(), n grid[0].size(); vectorvectorbool visited(m, vectorbool(n, false)); // 第一步从四条边界的陆地出发标记所有非孤岛连通块 for (int i 0; i m; i) { if (grid[i][0] 1 !visited[i][0]) bfs(grid, visited, i, 0); if (grid[i][n - 1] 1 !visited[i][n - 1]) bfs(grid, visited, i, n - 1); } for (int j 0; j n; j) { if (grid[0][j] 1 !visited[0][j]) bfs(grid, visited, 0, j); if (grid[m - 1][j] 1 !visited[m - 1][j]) bfs(grid, visited, m - 1, j); } // 第二步剩下的未访问陆地就是孤岛 int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1 !visited[i][j]) { count; bfs(grid, visited, i, j); } } } return count; } private: void bfs(vectorvectorint grid, vectorvectorbool visited, int x, int y) { int m grid.size(), n grid[0].size(); queuepairint, int q; q.push({x, y}); visited[x][y] true; int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; while (!q.empty()) { auto [cx, cy] q.front(); q.pop(); for (auto d : dirs) { int nx cx d[0]; int ny cy d[1]; if (nx 0 || nx m || ny 0 || ny n) continue; if (grid[nx][ny] 1 !visited[nx][ny]) { visited[nx][ny] true; q.push({nx, ny}); } } } } };如果你更喜欢 DFS只需要把bfs函数换成递归版本主体流程完全不变。4.2 用一张小图完整跑一遍算法流程拿这个简单例子走一遍0 0 1 0 1 1 0 0 0 0 0 1 1 0 1 1第一步遍历四条边界第一行(0,2)是陆地启动 BFS。它只和(1,2)相邻但(1,2)是水所以这个连通块只有自己。标记visited[0][2]。第一列(1,0)是陆地启动 BFS。它能走到(1,1)但(1,1)是水所以又是个单点标记。最后一行(3,0)是陆地启动 BFS。它往下越界往右是水标记。最后一列(2,3)是陆地启动 BFS。它能走到(3,3)(3,3)又能走到(3,2)这三个格子组成一个连通块全部标记。同时(0,3)是水跳过。第二步全图遍历(0,2)已标记跳过。第一行剩下(0,0)和(0,1)都是水跳过。(1,0)、(1,1)中(1,0)已标记但(1,1)是水跳过。第二行(2,0)是水(2,1)是水(2,2)是水(2,3)已标记。第三行(3,0)已标记(3,1)是水(3,2)已标记(3,3)已标记。遍历结束没有发现任何未访问的陆地所以答案是 0。这和我前面说的“边界连通块优先处理”逻辑完全一致。4.3 模板化“边界标记”思路一套代码打天下等你把上面的代码写顺手之后会发现它其实能复用到很多题。比如 LeetCode 130 被围绕的区域要求把被 X 包围的 O 全部改成 X核心做法就是从边界的 O 反向标记剩余 O 才需要翻转。再比如 LeetCode 1020 飞地的数量把边界 1 标完统计剩余 1 的数量。这些题本质上真的是同一套模板。我一般会在本地维护一个“网格连通题”的代码片段里面放上 BFS 的模板函数需要时直接复制再改改判断条件。刷题效率能提升不少。5. 我在提交过程中踩过的三个坑每一个都让我debug到怀疑人生5.1 第一个坑只标记边界格子没有对整个连通块做标记这是我初学孤岛题时犯的第一个错误。我当时想的是把网格四条边上是 1 的格子单独标记一下遍历的时候只要看到陆地旁边有边界陆地就认为它属于边界连通块。这个思路在“边界格子旁边没有内部连接”的简单例子里能过但一旦遇到边界陆地向内部延伸出一条通道内部那个格子明明和边界连通块相连却因为自己不贴边被错误地当成了孤岛。正确做法是从边界格子出发后一定要做完整的 DFS/BFS 扩散把整个连通块全部标记。不能只看格子本身是否贴边要看它整个“家族”是否贴边。这就是我第一次意识到“连通块”和“单个格子”在网格题里的区别。5.2 第二个坑BFS 里重复入队导致死循环写 BFS 的时候有个经典错误在从队列取出节点时才标记 visited而不是在压入队列时就标记。这样会导致同一个节点被多个相邻节点重复压入队列虽然最终不会死循环但效率会差很多极端情况下甚至能撑爆队列。正确姿势是在将一个格子压入队列的那一刻就立刻标记 visited。这也是很多 BFS 模板特别强调的一点。因为网格是二维的一个格子最多有四个邻居如果没有及时标记它可能被上下左右四个方位各压入一次白白浪费空间和时间。我当时踩这个坑是在一个 500×500 的全陆地矩阵上运行时间直接慢了好几倍。改成入队即标记之后快得飞起。5.3 第三个坑方向数组写错导致漏掉连通块方向数组看起来简单但特别容易写错。我自己的教训是dirs[4][2]四个方向只写了三个漏了向上结果所有往上延伸的连通块都断掉了。这种错误在小型测试用例上非常难发现因为恰好你的测试数据没有“必须向上才能连接”的形状。为了彻底解决这个问题我后来养成了一个习惯每次写网格题之前先把四个方向在纸上画一遍或者直接在代码里写全四个方向再检查一遍下标。甚至见过有人把方向数组写成下面的常量表达式int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};这个顺序本身没问题但关键是你要形成肌肉记忆不给漏写留机会。5.4 额外的一个提醒别把 row 和 col 搞反大一维数组坐标转二维的时候idx i * n j只适用于按行存储的情况。如果你用并查集需要把二维(i, j)转换成一维节点编号这里特别容易把i * n j写成i * m j。一旦写错代码运行结果会非常随机debug 起来让人抓狂。我的建议是在并查集代码里维护一个内联函数int index(int i, int j) { return i * n j; }然后把所有转换都走这个函数尽量别手写两遍。6. 从“孤岛基础”延伸出去变形题、面试表达与扩展思路6.1 变体一求孤岛总面积LeetCode 1020 飞地的数量这道题基本就是“孤岛基础”换了个问法不统计孤岛数量而是统计所有孤岛上的陆地格子总数。解法流程完全一样先把边界陆地连通块标记再遍历剩下未访问的陆地数量。代码上只需要把最后一步的count改成area就可以了。如果你理解了孤岛题的标记逻辑这道题属于免费赠送。6.2 变体二把孤岛填成水域这种题会要求你直接修改原网格把所有孤岛变成 0。常见错误是遍历到孤岛后马上调用 DFS/BFS 把它改掉结果在遍历过程中原网格一直在变导致遍历逻辑混乱。更稳妥的做法是分两步第一遍先把边界连通块标记掉第二遍再遍历所有陆地且只对“非边界标记”的陆地执行填充操作。这样填充过程不会干扰边界连通块的状态。6.3 变体三多条边界、多个岛屿之间的连通性有些更复杂的题会问“如果去掉某些水域有多少个岛屿连到一起”之类的问题这时候 DFS/BFS 的单次遍历就不够用了需要并查集配合动态更新。但核心仍然是“连通块”这个基础概念。所以我在刷题时会把“孤岛基础”当作第一个里程碑它验证你对连通块的标记、边界条件的处理、DFS/BFS 两种遍历方式的切换是否熟练。这些能力在后续几乎所有网格题里都是必需品。6.4 面试时怎么说才能加分如果面试官让你讲讲孤岛题的思路不要只背解法可以按这个层次来讲先一句话定义“孤岛不接触边界的陆地连通块”然后指出“正向找孤岛很难判断边界反向标记边界连通块更简单”再补充一句“边界标记和后续统计各用一次 DFS/BFS整体复杂度 O(m×n)”最后可以提一句“如果矩阵特别大我会用 BFS 代替递归 DFS 防止栈溢出”。这套表达方式会把你的思路组织得特别清晰面试官能快速抓住重点你也不容易在细节描述里跑偏。写到这里回头再看“图论Day38孤岛基础”这个题目其实真正让人成长的不是孤岛有多少个、面积有多大而是“从边界反向思考”这个思维模型的建立。我在刷这道题之前遇到什么问题第一反应都是正向硬解刷完之后很多连通性题目我都会先问一句“能不能从边界下手”。这个小习惯比多刷十道题都值。如果你也在刷图论建议把孤岛题当作一个重要节点写进自己的刷题笔记里没事翻一翻会有新的理解。