企业官网建设流程全解析

刷图论题最烦什么？不是题不会做，而是代码写完觉得天衣无缝，一跑测试用例就崩，最后发现是方向数组写错了或者边界判断漏了一条。今天这两道题——99. 岛屿数量（深搜、广搜）和100. 岛屿的最大面积，恰好就是检验你有没有踩稳图论基础的标尺。代码随想录算法训练营排到第五十六天，已经默认你对递归、队列、二维数组这些基本功掌握了，但说实话，这两道题恰恰能把很多刷了上百题的人打回原形。我之前带过不少训练营的学员，有人写了三年业务代码，拿到“岛屿数量”还是会在visited数组的标记时机上栽跟头。

这两道题本质上是同一个模型：二维矩阵里有陆地和海水，把连成片的陆地当成一个岛屿，让你数一共有多少个岛屿，或者找出面积最大的那块陆地有多大。听起来简单，但它把图论里两个最核心的遍历方式——深度优先搜索（DFS）和广度优先搜索（BFS）——都考到了。而且它们是从“图”到“网格图”的桥头堡，后面LeetCode上那些经典题（被围绕的区域、飞地的数量、岛屿的周长、最大人工岛）全是这两题的变体。这篇文章我会把深搜和广搜两条路都走一遍，把每行代码为什么这么写讲清楚，也把面试里最容易失分的细节挨个点名。

1. 岛屿类问题为什么是图论入门必刷题

1.1 从题目表面看本质：连通分量计数

先别看题目觉得“就是数数而已”，我们把这个模型抽象出来看。一个N行M列的矩阵，每个格子是0或1，0是海水，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里最常见的三连判断：

1. 是否越界——出界了直接跳过
2. 是否已经访问过——访问过就跳过
3. 是否是陆地——是海水就跳过

三个条件全部满足，才能递归往下走。这套写法在代码随想录里叫“先检查再递归”，比“先递归再检查”更省栈空间，也更符合人的直觉。

2.2 visited标记的正确时机

这个点必须单独拿出来讲，因为它在训练营第五十六天这个节点上，仍然会有人犯错。

正确的做法是：在调用dfs之前，就把当前格子的visited标记为true，也就是主循环里的visited[i][j] = true，以及递归前visited[nextX][nextY] = true。

为什么不能在进入dfs之后再标记当前的格子？

我们看一个场景：从格子A进入dfs，dfs里枚举四个方向，发现格子B是陆地且未访问，于是先标记B为已访问，再递归进入B。假设我们在进入B的dfs之前没有标记B，那么当A还在枚举其他方向时，万一另一个方向的格子C也相邻于B，C的搜索路径可能会把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) { Queue<int[]> 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); } }

队列用Queue<int[]>来存格子坐标，每次从队头取出一个格子，枚举它的四个方向，把符合条件的邻居格子“标记之后入队”。整个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发现邻居C，C入队；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); } }

核心改动只有三处：

1. 类里加了一个静态变量area作为当前岛屿的面积计数器
2. dfs函数每次进入一个格子，area++
3. 主循环里每次发现新岛屿，先把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) { Queue<int[]> 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后M，N是行数，M是列数。但有人扫描输入的时候顺手写了grid[m][n]，结果数组越界或者逻辑错乱。这题N和M的范围一般不大，越界时还能当场发现；一旦数据填对了但数组长宽对调了，行为会非常诡异，排查半天才发现是grid.length和grid[0].length拿反了。

第二，方向数组写漏或多写。有人写{{0,1},{1,0},{0,-1}}少了一条向上，结果遇到某些岛屿形状，就有一部分陆地永远访问不到，导致岛屿数量比预期多。这种错很难靠看代码发现，只能靠测试用例覆盖。我自己的习惯是把方向数组固定成“上、右、下、左”的顺序，每次默写都不变，降低出错概率。

第三，主循环里忘了初始化visited。这道题你从主循环进入DFS/BFS之前，必须把当前格子标记为true。我见过有人只在递归函数里标记，主循环里不标记，结果第一个格子被重复计数，甚至导致死循环。

第四，BFS队列里存了二维坐标但不知道队列元素类型怎么定义。在Java里可以用Queue<int[]>，也可以用Queue<Pair>，后者需要额外定义类。C++里用queue<pair<int,int>>最自然。Python里可以用collections.deque装元组。这个属于语言的API熟练度问题，平时写代码要多留意，别到了考场才想。

第五，边界判断冗余或错误。有的同学喜欢在DFS入口处判断越界后再return，这是一种写法；我上面给的写法是在访问邻居之前判断邻居是否越界。两种都对，但不要混着写，不然很容易出“入口处判断了越界，循环里没有判断，导致数组越界”的bug。

5.3 从岛屿数量到衍生题目的迁移能力

最后我想说一个很重要的点：刷完这两道题，你的收获不应该只是“会写DFS和BFS模板”，而是拥有了一套迁移能力。

LeetCode上有很多类似的网格搜索题，底层都是这两个模板：

• 200. 岛屿数量：一模一样，直接套DFS/BFS
• 695. 岛屿的最大面积：一模一样，加上面积统计
• 463. 岛屿的周长：DFS遍历时，遇到海水格子或越界就周长加1
• 130. 被围绕的区域：先从边界DFS标记特殊符号，再遍历整个矩阵把没标记的O变成X
• 1020. 飞地的数量：先去掉边界能到达的陆地，再数剩余陆地
• 827. 最大人工岛：核心思路是给每个岛屿编号并记录面积，再枚举每个海洋格子连接四周岛屿的潜在面积

这些题没有一道是需要你重新发明算法的，全部是“基础模板 + 一个小变形”。所以训练营之前反复强调二刷三刷，不是让你背题，是让你把模板内化成肌肉记忆，这样遇到新题，你第一时间就知道该往哪个方向使劲。

我个人刷这套题的经验是：不要只写一遍，至少写三遍。第一遍看着题解写，第二遍合上书默写，第三遍限时15分钟写两道题。等你三遍都能稳稳AC后，再去碰那些衍生题，你会发现每道题都像是老朋友。

最后补一句大实话：第五十六天意味着训练营已经进入中后期，体力上可能有点疲劳，但图论这关必须硬啃下来。岛屿数量这两题过了，后面处理更复杂的拓扑排序、最短路径、最小生成树，至少你的遍历骨架不会再出问题。所以今天别图快，DFS和BFS两个版本都亲手敲一遍，最好再各改出三五个变种跑一跑——这个时间花得绝对值。