刷图论题最烦什么不是题不会做而是代码写完觉得天衣无缝一跑测试用例就崩最后发现是方向数组写错了或者边界判断漏了一条。今天这两道题——99. 岛屿数量深搜、广搜和100. 岛屿的最大面积恰好就是检验你有没有踩稳图论基础的标尺。代码随想录算法训练营排到第五十六天已经默认你对递归、队列、二维数组这些基本功掌握了但说实话这两道题恰恰能把很多刷了上百题的人打回原形。我之前带过不少训练营的学员有人写了三年业务代码拿到“岛屿数量”还是会在visited数组的标记时机上栽跟头。这两道题本质上是同一个模型二维矩阵里有陆地和海水把连成片的陆地当成一个岛屿让你数一共有多少个岛屿或者找出面积最大的那块陆地有多大。听起来简单但它把图论里两个最核心的遍历方式——深度优先搜索DFS和广度优先搜索BFS——都考到了。而且它们是从“图”到“网格图”的桥头堡后面LeetCode上那些经典题被围绕的区域、飞地的数量、岛屿的周长、最大人工岛全是这两题的变体。这篇文章我会把深搜和广搜两条路都走一遍把每行代码为什么这么写讲清楚也把面试里最容易失分的细节挨个点名。1. 岛屿类问题为什么是图论入门必刷题1.1 从题目表面看本质连通分量计数先别看题目觉得“就是数数而已”我们把这个模型抽象出来看。一个N行M列的矩阵每个格子是0或10是海水1是陆地。所有相邻上下左右对角线不算的1组成一个岛屿。统计岛屿数量本质上就是在做一个连通分量的计数——把二维矩阵看成一个图每个格子是一个节点相邻的陆地节点之间有一条边那么一个岛屿就是图中的一个连通分量。这个认知很重要因为一旦你意识到这一点整个思路就清晰了遍历整个矩阵的每一个格子遇到一个没访问过的陆地就说明发现了一个新岛屿数量加1然后从这个格子出发把整个岛屿的所有陆地全部“标记”为已访问免得后面重复计数。我第一次跟学员讲这个思路的时候有人问“那我直接拿一个变量记录每个岛屿的编号把同一个岛屿的格子都改成同一个数字不也行吗”答案是可以的本质上是一样的逻辑只是额外开辟了空间记录编号。标准解法里用的visited布尔数组其实等价于给每个格子打一个“是否已经被某个岛屿认领”的标记。1.2 训练营第五十六天的排兵布阵逻辑代码随想录把这两道题放在一起不是随手的。岛屿数量是“模板题”用来建立网格图的DFS/BFS基本套路岛屿的最大面积则是“模板上加一点变化”在遍历的同时记录统计信息。这两道题的前后顺序其实暗含了一个学习曲线先掌握遍历的骨架方向数组 递归或队列 visited标记再掌握在遍历中携带信息面积累加、最大面积比较这个设计逻辑跟LeetCode上的阵列是一脉相承的。LeetCode 200岛屿数量是经典中的经典695岛屿最大面积比它多了个统计逻辑。所以你要是把这两道卡码网的题吃透了再去刷LeetCode的这两道几乎没有额外成本只需要调整输入输出格式就行。这就是为什么训练营里大家常说“吃透一个模板解决一整类题”的真正含义。2. 深搜DFS解决岛屿数量的完整实现2.1 方向数组与递归框架设计我先把完整代码贴出来再逐段拆import java.util.*; public class Main { static int[][] dir {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; static void dfs(int[][] grid, boolean[][] visited, int x, int y) { for (int i 0; i 4; i) { int nextX x dir[i][0]; int nextY y dir[i][1]; if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length) { continue; } if (!visited[nextX][nextY] grid[nextX][nextY] 1) { visited[nextX][nextY] true; dfs(grid, visited, nextX, nextY); } } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] grid new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { grid[i][j] sc.nextInt(); } } boolean[][] visited new boolean[n][m]; int result 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (!visited[i][j] grid[i][j] 1) { result; visited[i][j] true; dfs(grid, visited, i, j); } } } System.out.println(result); } }核心就是那个4元素的方向数组{0,1} → 向右 {1,0} → 向下 {-1,0} → 向上 {0,-1} → 向左这玩意是网格DFS的地基。方向数组的顺序无所谓但建议固定成一个习惯这样写代码的时候不用每次重新想。有的同学喜欢把方向数组定义为{{1,0},{-1,0},{0,1},{0,-1}}也完全没问题关键是四条方向都要覆盖不能漏。进入DFS函数后for循环枚举四个方向每个方向算出一个新坐标newX, newY。接下来是DFS里最常见的三连判断是否越界——出界了直接跳过是否已经访问过——访问过就跳过是否是陆地——是海水就跳过三个条件全部满足才能递归往下走。这套写法在代码随想录里叫“先检查再递归”比“先递归再检查”更省栈空间也更符合人的直觉。2.2 visited标记的正确时机这个点必须单独拿出来讲因为它在训练营第五十六天这个节点上仍然会有人犯错。正确的做法是在调用dfs之前就把当前格子的visited标记为true也就是主循环里的visited[i][j] true以及递归前visited[nextX][nextY] true。为什么不能在进入dfs之后再标记当前的格子我们看一个场景从格子A进入dfsdfs里枚举四个方向发现格子B是陆地且未访问于是先标记B为已访问再递归进入B。假设我们在进入B的dfs之前没有标记B那么当A还在枚举其他方向时万一另一个方向的格子C也相邻于BC的搜索路径可能会把B再次当作未访问的陆地处理造成重复递归。画个简单的图A B D C这是一个2×2的小矩阵A、B、C、D都是陆地但A只和B、D相邻B只和A、C相邻等等。如果从A开始搜索A先向右走发现B如果此时不标记B就直接dfs(B)那么dfs(A)在处理完右边之后还会处理下面D此时没有影响。但如果矩阵再大一点存在环状的陆地结构DFS就可能在环上反复绕造成无限递归。在某个格子进入递归队列之前就必须把它标记为已访问这是DFS和BFS通用的黄金法则。你可以这样记凡是进入搜索的节点必须“先登记再出门”不能出门之后再回头登记否则就会有人重复上门。2.3 完整代码与时间复杂度分析上面代码在卡码网提交能直接通过。时间复杂度是O(N×M)因为每个格子最多被访问一次主循环是N×M次递归里的for循环每个格子最多枚举4个方向所以总操作量是4×N×M常数级别的差距不影响量级。空间复杂度方面递归栈的最深深度在最坏情况下能到N×M比如整个矩阵全是陆地并且形状是一条蛇形但Java默认栈大小基本能承受几千量级的递归深度。如果题目把矩阵规模扩大到10^4级别那就得考虑用BFS来规避递归栈溢出的风险了这个我在后面章节会细说。3. 广搜BFS解决岛屿数量与队列陷阱3.1 BFS模板队列的入队与标记时机DFS适合“一条路走到黑”BFS则适合“一层一层往外扩”。岛屿数量这题用BFS写起来的骨架是这样的import java.util.*; public class Main { static int[][] dir {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; static void bfs(int[][] grid, boolean[][] visited, int x, int y) { Queueint[] queue new LinkedList(); queue.offer(new int[]{x, y}); visited[x][y] true; while (!queue.isEmpty()) { int[] cur queue.poll(); int curX cur[0]; int curY cur[1]; for (int i 0; i 4; i) { int nextX curX dir[i][0]; int nextY curY dir[i][1]; if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length) { continue; } if (!visited[nextX][nextY] grid[nextX][nextY] 1) { visited[nextX][nextY] true; queue.offer(new int[]{nextX, nextY}); } } } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] grid new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { grid[i][j] sc.nextInt(); } } boolean[][] visited new boolean[n][m]; int result 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (!visited[i][j] grid[i][j] 1) { result; bfs(grid, visited, i, j); } } } System.out.println(result); } }队列用Queueint[]来存格子坐标每次从队头取出一个格子枚举它的四个方向把符合条件的邻居格子“标记之后入队”。整个while循环直到队列为空说明当前这个连通分量岛屿已经被完整遍历完了。3.2 经典失误为什么不能弹出时才标记visited这里必须强调一个我在训练营答疑时反复纠正过的坑千万不能在poll弹出的时候才标记visited。错误写法长这样while (!queue.isEmpty()) { int[] cur queue.poll(); visited[cur[0]][cur[1]] true; // 错误示范 // ... }表面上看没问题弹出的时候标记也不晚。但问题是一个格子可能在弹出之前就被不同的邻居重复加入队列。举个例子A D B C假设A入队B和D都是A的邻居。正常的入队流程应该是A入队并标记visited弹出A时发现B和D未访问于是B和D都入队并标记visited。但如果不在入队时标记而是在弹出时标记那B在A弹出时入队D也在A弹出时入队B和D都没有被标记为visited接着B先弹出B发现邻居CC入队D弹出时D也发现邻居C——此时C已经被B入队了但因为没有标记D会把C再次入队。结果就是队列里有重复的C重复的访问带来重复的遍历虽然最终可能不会死循环因为弹出时总会标记但会造成大量的重复计算性能严重下降极端情况下队列里会塞满重复坐标甚至因为标记时机不对导致程序行为不可预测。所以记住一句话BFS的visited标记必须发生在offer入队的那一刻而不是poll出队的那一刻。这是BFS区别于DFS的一个核心编写规范也是代码随想录里反复强调的“一个元素入队时就应该标记”的底层原因。3.3 双版本对比DFS与BFS的差异点用同一道题同时跑DFS和BFS能直观感受到两种策略。DFS代码短、逻辑直白适合“从当前点出发把能走的路都走完再回头”BFS代码稍长但层次感强适合需要“先近后远”的场景。在岛屿数量这个题目上两者时间复杂度一样实际运行时间差距也不大。但站在面试的角度面试官经常会追问“你既然会DFS为什么这题不用BFS或者反过来。”你不能说“因为模板里写的DFS我就用DFS”。你要能说出适用场景的差异DFS适合求连通块、检测环路等场景代码简单但递归深度受栈空间限制蛇形大矩阵可能导致栈溢出BFS适合求最短路径、逐层扩展的场景使用队列不担心栈溢出但代码相对繁琐网格类的图论题两种都要能默写。4. 岛屿最大面积一句话改造你的搜索逻辑4.1 在DFS骨架里加计数器第二题是在第一题的基础上做了一个简单的“统计增强”——每个岛屿不再只是“发现”那么简单还要算出这个岛屿包含多少块陆地然后在所有岛屿里取最大值。DFS版本我直接给代码import java.util.*; public class Main { static int[][] dir {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; static int area; static void dfs(int[][] grid, boolean[][] visited, int x, int y) { area; for (int i 0; i 4; i) { int nextX x dir[i][0]; int nextY y dir[i][1]; if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length) { continue; } if (!visited[nextX][nextY] grid[nextX][nextY] 1) { visited[nextX][nextY] true; dfs(grid, visited, nextX, nextY); } } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] grid new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { grid[i][j] sc.nextInt(); } } boolean[][] visited new boolean[n][m]; int maxArea 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (!visited[i][j] grid[i][j] 1) { area 0; visited[i][j] true; dfs(grid, visited, i, j); maxArea Math.max(maxArea, area); } } } System.out.println(maxArea); } }核心改动只有三处类里加了一个静态变量area作为当前岛屿的面积计数器dfs函数每次进入一个格子area主循环里每次发现新岛屿先把area清零再DFS结束后用Math.max更新全局最大值这个思路的妙处在于遍历骨架完全不变只是往节点进入的时机“插入”一个计数操作。这种思路可以推广到很多变式题——比如统计岛屿的周长、统计岛屿的坐标集合、找出岛屿边界格子的数量等等。4.2 免visited的原地标记法及其风险还有一条路不用visited数组直接把已经访问过的陆地改成0海水相当于“淹掉”这个格子。static int dfs(int[][] grid, int x, int y) { if (x 0 || x grid.length || y 0 || y grid[0].length || grid[x][y] 0) { return 0; } grid[x][y] 0; return 1 dfs(grid, x 1, y) dfs(grid, x - 1, y) dfs(grid, x, y 1) dfs(grid, x, y - 1); }这种写法非常简洁而且不需要额外的visited数组。LeetCode的695题很多人就是这么写的提交也能过。但在训练营的代码规范里我不太推荐在练习阶段用这种写法原因有三个一是可读性不如visited数组直观。别人看你代码可能要想一下才知道“原来你改grid是为了标记访问”。二是会污染输入数据。如果后续还有别的逻辑需要用到原始的矩阵数据原地修改会让你后悔。三是边界情况更难调试。当你把所有陆地改成0之后出了问题很难从中间状态推断哪里访问过、哪里没访问过。不过在纯算法竞赛场景下这种写法写起来最快、最省内存也算是一个值得掌握的技巧。我的建议是平时练习用visited数组版本笔试抢时间的时候可以切到原地标记版本。4.3 最大面积的BFS实现BFS版本和DFS版本只差一个“统计面积”的动作import java.util.*; public class Main { static int[][] dir {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; static int bfs(int[][] grid, boolean[][] visited, int x, int y) { Queueint[] queue new LinkedList(); queue.offer(new int[]{x, y}); visited[x][y] true; int area 0; while (!queue.isEmpty()) { int[] cur queue.poll(); area; for (int i 0; i 4; i) { int nextX cur[0] dir[i][0]; int nextY cur[1] dir[i][1]; if (nextX 0 || nextX grid.length || nextY 0 || nextY grid[0].length) { continue; } if (!visited[nextX][nextY] grid[nextX][nextY] 1) { visited[nextX][nextY] true; queue.offer(new int[]{nextX, nextY}); } } } return area; } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] grid new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { grid[i][j] sc.nextInt(); } } boolean[][] visited new boolean[n][m]; int maxArea 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (!visited[i][j] grid[i][j] 1) { maxArea Math.max(maxArea, bfs(grid, visited, i, j)); } } } System.out.println(maxArea); } }BFS的计数逻辑放在poll之后因为每从队列里弹出一个格子就代表这块陆地被遍历到了面积加1。这和DFS的area放在函数开头是同一个道理——进入某个格子时计数。注意这里不要在offer的时候计数否则同一个格子被重复offer时虽然我们在入队时已经标记visited理论上不会重复offer但计数逻辑放在poll处更保险语义也更清晰。5. 深搜广搜的选型依据与常见踩坑复盘5.1 什么场景选DFS、什么场景选BFS把两个版本的代码都写完你可能会问那我到底用哪个我的建议是有一套判断逻辑题干要求“有没有”“有多少个”比如岛屿数量、判环、查找连通性——DFS和BFS都行看你对哪个更熟练建议两个都熟练题干要求“最短”“最少步数”“最近距离”——比如迷宫最短路径、单词接龙、打开转盘锁——优先BFS因为BFS天然按层扩展第一次到达目标节点时的层数一定是最短路径题干给的矩阵特别大递归深度可能上万——优先BFS避免栈溢出题目要求输出所有路径、列举组合——优先DFS因为它更好记录路径历史放在代码随想录训练营的语境下第五十六天的要求就是两种写法都要能5分钟内默写出来。你不光要会还要能在脑子里快速做这个选择题。5.2 训练中最容易出现的几个低级错误刷题群里最常见的报错我一一列一下看看你中招过没有第一行和列读反了。输入格式是先N后MN是行数M是列数。但有人扫描输入的时候顺手写了grid[m][n]结果数组越界或者逻辑错乱。这题N和M的范围一般不大越界时还能当场发现一旦数据填对了但数组长宽对调了行为会非常诡异排查半天才发现是grid.length和grid[0].length拿反了。第二方向数组写漏或多写。有人写{{0,1},{1,0},{0,-1}}少了一条向上结果遇到某些岛屿形状就有一部分陆地永远访问不到导致岛屿数量比预期多。这种错很难靠看代码发现只能靠测试用例覆盖。我自己的习惯是把方向数组固定成“上、右、下、左”的顺序每次默写都不变降低出错概率。第三主循环里忘了初始化visited。这道题你从主循环进入DFS/BFS之前必须把当前格子标记为true。我见过有人只在递归函数里标记主循环里不标记结果第一个格子被重复计数甚至导致死循环。第四BFS队列里存了二维坐标但不知道队列元素类型怎么定义。在Java里可以用Queueint[]也可以用QueuePair后者需要额外定义类。C里用queuepairint,int最自然。Python里可以用collections.deque装元组。这个属于语言的API熟练度问题平时写代码要多留意别到了考场才想。第五边界判断冗余或错误。有的同学喜欢在DFS入口处判断越界后再return这是一种写法我上面给的写法是在访问邻居之前判断邻居是否越界。两种都对但不要混着写不然很容易出“入口处判断了越界循环里没有判断导致数组越界”的bug。5.3 从岛屿数量到衍生题目的迁移能力最后我想说一个很重要的点刷完这两道题你的收获不应该只是“会写DFS和BFS模板”而是拥有了一套迁移能力。LeetCode上有很多类似的网格搜索题底层都是这两个模板200. 岛屿数量一模一样直接套DFS/BFS695. 岛屿的最大面积一模一样加上面积统计463. 岛屿的周长DFS遍历时遇到海水格子或越界就周长加1130. 被围绕的区域先从边界DFS标记特殊符号再遍历整个矩阵把没标记的O变成X1020. 飞地的数量先去掉边界能到达的陆地再数剩余陆地827. 最大人工岛核心思路是给每个岛屿编号并记录面积再枚举每个海洋格子连接四周岛屿的潜在面积这些题没有一道是需要你重新发明算法的全部是“基础模板 一个小变形”。所以训练营之前反复强调二刷三刷不是让你背题是让你把模板内化成肌肉记忆这样遇到新题你第一时间就知道该往哪个方向使劲。我个人刷这套题的经验是不要只写一遍至少写三遍。第一遍看着题解写第二遍合上书默写第三遍限时15分钟写两道题。等你三遍都能稳稳AC后再去碰那些衍生题你会发现每道题都像是老朋友。最后补一句大实话第五十六天意味着训练营已经进入中后期体力上可能有点疲劳但图论这关必须硬啃下来。岛屿数量这两题过了后面处理更复杂的拓扑排序、最短路径、最小生成树至少你的遍历骨架不会再出问题。所以今天别图快DFS和BFS两个版本都亲手敲一遍最好再各改出三五个变种跑一跑——这个时间花得绝对值。