LeetCode 200. 岛屿数量：DFS与BFS双解法详解

在LeetCode的数组与矩阵类题目中，「200. 岛屿数量」是经典的图遍历入门题，核心考察深度优先搜索（DFS）和广度优先搜索（BFS）的实际应用。这道题难度适中，但能帮我们快速掌握“连通区域计数”的核心思路，今天就来详细拆解这道题，以及两种主流解法的实现逻辑。

一、题目解读

题目给出一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，要求计算网格中岛屿的数量。

关键规则说明：

• 岛屿由水平或竖直方向相邻的陆地（‘1’）连接形成，斜向相邻的不算。

• 网格的四条边均被水包围，无需考虑边界外的陆地。

举个简单例子：若网格为 [["1","1","0"],["1","1","0"],["0","0","1"]]，则有2个岛屿——左上角4个相邻的’1’构成一个岛屿，右下角1个’1’构成另一个岛屿。

二、核心思路

岛屿计数的本质是「寻找所有连通的’1’区域」，每找到一个未被访问过的’1’，就意味着发现了一个新岛屿，随后通过遍历（DFS/BFS）将这个岛屿上所有相邻的’1’标记为已访问，避免重复计数。

核心步骤：

这里用到「访问标记」（本题用Set实现），目的是避免同一陆地被多次遍历，提高效率并防止死循环。

三、解法一：深度优先搜索（DFS）

3.1 解法思路

DFS（深度优先搜索）的核心是「递归遍历」：找到一个未访问的’1’后，递归访问它的上下左右四个方向的单元格，直到遇到水（‘0’）或已访问的陆地，再回溯到上一层，继续遍历其他方向。

可以理解为“一条路走到黑，走不通再回头”，适合处理连通区域的遍历。

3.2 完整代码

function numIslands_1(grid: string[][]): number {
// 边界判断：网格为空或行长度为0，直接返回0
if (grid.length === 0 || grid[0].length === 0) {
return 0;
}
const rows = grid.length; // 网格行数
const cols = grid[0].length; // 网格列数
const visited = new Set<string>(); // 存储已访问的陆地坐标，格式为"i-j"

// 递归辅助函数：遍历当前陆地的所有相邻陆地
const helper = (grid: string[][], i: number, j: number) => {
// 终止条件：越界、当前是水、已访问过，直接返回
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] === '0' || visited.has(`${i}–${j}`)) {
return;
}
visited.add(`${i}–${j}`); // 标记当前陆地为已访问
// 递归访问上下左右四个方向
helper(grid, i + 1, j); // 下
helper(grid, i – 1, j); // 上
helper(grid, i, j + 1); // 右
helper(grid, i, j – 1); // 左
}

let count = 0; // 岛屿数量计数器
// 遍历整个网格
for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
// 找到未访问的陆地，计数+1，并触发DFS遍历整个岛屿
if (grid[i][j] === '1' && !visited.has(`${i}–${j}`)) {
helper(grid, i, j);
count++;
}
}
}

return count;
};

3.3 代码逐行解析

• 边界判断：先判断网格是否为空，若为空直接返回0，避免后续报错。

• visited集合：用“行索引-列索引”的字符串格式（如"0-1"）存储已访问的陆地，确保每个坐标唯一。

• helper递归函数：核心遍历逻辑，先判断当前坐标是否合法（不越界、是陆地、未访问），合法则标记访问，再递归访问四个方向。

• 双重循环遍历网格：逐个检查每个单元格，发现未访问的陆地时，计数+1，并调用helper遍历整个岛屿，确保该岛屿的所有陆地都被标记为已访问。

四、解法二：广度优先搜索（BFS）

4.1 解法思路

BFS（广度优先搜索）的核心是「队列遍历」：找到一个未访问的’1’后，将其加入队列，然后依次取出队列中的每个坐标，访问它的上下左右四个方向的陆地，符合条件的陆地加入队列并标记为已访问，直到队列为空，即完成一个岛屿的遍历。

可以理解为“从中心向外扩散，逐层遍历”，适合处理层次化的遍历场景，也能有效避免递归栈溢出（对于极大的网格，DFS可能出现栈溢出，BFS更稳定）。

4.2 完整代码

function numIslands_2(grid: string[][]): number {
// 边界判断，与DFS一致
if (grid.length === 0 || grid[0].length === 0) {
return 0;
}
const rows = grid.length;
const cols = grid[0].length;
const visited = new Set<string>();
let count = 0;

for (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === '1' && !visited.has(`${i}–${j}`)) {
count++; // 发现新岛屿，计数+1
const queue = [[i, j]]; // 初始化队列，存入当前陆地坐标
visited.add(`${i}–${j}`); // 标记为已访问

// 队列不为空，持续遍历
while (queue.length) {
const [x, y] = queue.shift()!; // 取出队列头部坐标（FIFO）
// 检查上方陆地
if (x > 0 && grid[x – 1][y] === '1' && !visited.has(`${x – 1}–${y}`)) {
visited.add(`${x – 1}–${y}`);
queue.push([x – 1, y]);
}
// 检查下方陆地
if (x < rows – 1 && grid[x + 1][y] === '1' && !visited.has(`${x + 1}–${y}`)) {
visited.add(`${x + 1}–${y}`);
queue.push([x + 1, y]);
}
// 检查左侧陆地
if (y > 0 && grid[x][y – 1] === '1' && !visited.has(`${x}–${y – 1}`)) {
visited.add(`${x}–${y – 1}`);
queue.push([x, y – 1]);
}
// 检查右侧陆地
if (y < cols – 1 && grid[x][y + 1] === '1' && !visited.has(`${x}–${y + 1}`)) {
visited.add(`${x}–${y + 1}`);
queue.push([x, y + 1]);
}
}
}
}
}

return count;
};

4.3 代码逐行解析

• 边界判断和visited集合的作用，与DFS解法完全一致。

• 队列的作用：存储当前岛屿中待遍历的陆地坐标，遵循“先进先出”（FIFO）原则，确保逐层遍历。

• while循环：当队列不为空时，取出头部坐标，依次检查其上下左右四个方向的单元格，若为未访问的陆地，则标记访问并加入队列，直到队列清空，完成当前岛屿的遍历。

• 坐标合法性判断：每个方向都要检查是否越界（如x>0才会检查上方），避免数组越界报错。

五、两种解法对比

注意：两种解法的时间复杂度和空间复杂度一致，核心区别在于遍历方式和稳定性——BFS更适合大规模网格，避免DFS的递归栈溢出问题。

六、常见易错点

• 越界判断：忘记检查坐标是否超出网格范围（如i<0、i>=rows），导致数组越界报错。

• 访问标记遗漏：未标记已访问的陆地，导致同一陆地被多次遍历，计数错误。

• 方向遗漏：只遍历上下两个方向，忘记左右方向，导致岛屿未被完整遍历。

• 队列操作错误：BFS中用shift()取出队列头部（正确，FIFO），若误用pop()则变成DFS的逻辑。

七、总结

「岛屿数量」这道题的核心是「连通区域计数」，而DFS和BFS是解决这类问题的两大核心方法。通过这道题，我们可以掌握：

其实，这道题还有进阶解法（如并查集Union-Find），但DFS和BFS是最基础、最易理解的两种方式，适合入门练习。建议大家动手敲一遍代码，修改网格测试用例，感受两种遍历方式的差异，加深对图遍历的理解。