algorithms►leetcode

016-岛屿数量(DFS or BFS)

岛屿数量

问题描述

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，计算其中岛屿的数量。岛屿被水包围，并且通过水平或垂直方向上相邻的陆地连接形成。

解法思路

在 JavaScript 中，我们可以使用 深度优先搜索 (DFS) 或 广度优先搜索 (BFS) 来解决这个问题。这里我们主要介绍 DFS 解法，因为它代码简洁且易于理解。

核心思想

  1. 遍历网格：逐个检查每个格子。
  2. **发现陆地 (‘1’)**：每当发现一块未访问的陆地，岛屿计数加 1。
  3. 标记已访问：使用 DFS 或 BFS 把与该陆地相连的所有陆地标记为已访问（避免重复计数）。
  4. 继续遍历：直到整个网格遍历完成。

DFS 解法代码

方法 1：修改原数组（空间最优）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function numIslands(grid) {
    if (!grid || grid.length === 0) return 0;

    let count = 0;
    const rows = grid.length;
    const cols = grid[0].length;

    // DFS 辅助函数：把当前陆地及其相连陆地标记为 '0'（水）
    function dfs(r, c) {
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0') {
            return; // 越界或遇到水，直接返回
        }

        grid[r][c] = '0'; // 标记为已访问（改成水）

        // 递归搜索四个方向
        dfs(r + 1, c); // 下
        dfs(r - 1, c); // 上
        dfs(r, c + 1); // 右
        dfs(r, c - 1); // 左
    }

    // 遍历整个网格
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') { // 发现新岛屿
                count++;
                dfs(r, c); // 标记所有相连陆地
            }
        }
    }

    return count;
}

方法 2：不修改原数组（使用 visited 标记）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function numIslands(grid) {
    if (!grid || grid.length === 0) return 0;

    let count = 0;
    const rows = grid.length;
    const cols = grid[0].length;
    const visited = Array(rows).fill().map(() => Array(cols).fill(false));

    function dfs(r, c) {
        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] === '0' || visited[r][c]) {
            return; // 越界、水或已访问，直接返回
        }

        visited[r][c] = true; // 标记为已访问

        dfs(r + 1, c); // 下
        dfs(r - 1, c); // 上
        dfs(r, c + 1); // 右
        dfs(r, c - 1); // 左
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1' && !visited[r][c]) {
                count++;
                dfs(r, c);
            }
        }
    }

    return count;
}

BFS 解法（队列实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function numIslands(grid) {
    if (!grid || grid.length === 0) return 0;

    let count = 0;
    const rows = grid.length;
    const cols = grid[0].length;
    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // 四个方向

    function bfs(r, c) {
        const queue = [[r, c]];
        grid[r][c] = '0'; // 标记为已访问

        while (queue.length > 0) {
            const [currentR, currentC] = queue.shift();

            for (const [dr, dc] of directions) {
                const newR = currentR + dr;
                const newC = currentC + dc;

                if (newR >= 0 && newC >= 0 && newR < rows && newC < cols && grid[newR][newC] === '1') {
                    grid[newR][newC] = '0'; // 标记为已访问
                    queue.push([newR, newC]);
                }
            }
        }
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') {
                count++;
                bfs(r, c);
            }
        }
    }

    return count;
}

复杂度分析

方法 时间复杂度 空间复杂度
DFS O(M×N) O(M×N)（递归栈最坏情况）
BFS O(M×N) O(min(M, N))（队列存储）
  • DFS 适合代码简洁的场景，但递归可能导致栈溢出（极端情况下）。
  • BFS 用队列实现，适合大规模数据，空间复杂度更低。

示例测试

1
2
3
4
5
6
7
8
const grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
];

console.log(numIslands(grid)); // 输出: 3

总结

  • DFS 和 BFS 都能有效解决岛屿数量问题。
  • DFS 更简洁，适合面试快速编写。
  • BFS 空间更优，适合大规模数据。
  • 如果允许修改原数组，可以优化空间复杂度（无需额外 visited 数组）。

用生活化例子彻底搞懂DFS和BFS

1. 用现实生活比喻理解

DFS 就像走迷宫：

  • 你选择一条路一直走到底，如果走不通就回上一个岔路口
  • 带一根粉笔，走过的路都做标记（对应程序中的visited）
  • 特点：专注一条路，可能很快找到出口，也可能绕远路

BFS 就像撒网捕鱼：

  • 你同时向所有可能的方向撒网（一层层扩展）
  • 第一网抓1米内的鱼，第二网抓2米内的鱼…
  • 特点：总能找到最短路径，但需要更多”渔网”（内存）

2. 全新图解 - 以家庭派对为例

假设你要通知一个家族的所有成员来参加派对：

DFS方案（递归通知）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
graph TD
    A[爷爷] --> B[爸爸]
    B --> C[你]
    C --> D[儿子]
    D --> E[孙子]
    E -->|通知完回传| D
    D -->|通知完回传| C
    C --> F[女儿]
    F --> G[孙女]
    G -->|回传| F
    F -->|回传| C
    C -->|回传| B
    B --> H[叔叔]
    H --> I[堂弟]
    I -->|回传| H
    H -->|回传| B
    B -->|回传| A

特点：一个分支通知完才通知另一个分支

BFS方案（群发通知）：

1
2
3
4
5
6
graph TD
    A[第1层: 爷爷]
    A --> B[第2层: 爸爸,叔叔]
    B --> C[第3层: 你,堂弟]
    C --> D[第4层: 儿子,女儿]
    D --> E[第5层: 孙子,孙女]

特点：按辈分一层层通知，同辈人同时收到通知

3. 回到岛屿问题 - 一步一步手把手解析

示例网格：

[
 ['1','1','0','0'],
 ['1','0','1','1'],
 ['0','0','1','0']
]

DFS 执行步骤（带详细注释）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function dfs(grid, r, c) {
  // 1. 检查是否越界或是水
  if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] === '0') {
    return;
  }
  
  // 2. 标记当前为已访问（沉岛）
  grid[r][c] = '0'; 
  
  // 3. 向四个方向递归搜索
  dfs(grid, r + 1, c); // 下
  dfs(grid, r - 1, c); // 上
  dfs(grid, r, c + 1); // 右
  dfs(grid, r, c - 1); // 左
  // 注意：没有循环，纯靠递归栈回溯
}

具体执行顺序：

  1. 发现(0,0)是陆地，count=1
    • 沉没(0,0)，递归搜索↓
  2. 访问(1,0)（下方）
    • 沉没(1,0)，递归搜索↓
    • (2,0)是水，返回
    • 搜索↑(0,0)已沉没
    • 搜索→(1,1)是水
    • 搜索←(1,-1)越界
  3. 回到(0,0)的→方向(0,1)
    • 沉没(0,1)，递归搜索↓
    • (1,1)是水，返回
    • 其他方向都无效
  4. 继续扫描网格…
    • 发现(1,2)是新岛屿，count=2
    • 继续处理…

BFS 执行步骤（带详细注释）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function bfs(grid, r, c) {
  const queue = [[r, c]]; // 1. 初始化队列
  grid[r][c] = '0'; // 立即标记
  
  const directions = [[1,0],[-1,0],[0,1],[0,-1]]; // 2. 定义四个方向
  
  while (queue.length) {
    const [currR, currC] = queue.shift(); // 3. 取出队首
    
    for (const [dr, dc] of directions) { // 4. 检查四个方向
      const newR = currR + dr;
      const newC = currC + dc;
      
      if (newR >= 0 && newC >= 0 && 
          newR < grid.length && 
          newC < grid[0].length && 
          grid[newR][newC] === '1') {
        grid[newR][newC] = '0'; // 标记
        queue.push([newR, newC]); // 入队
      }
    }
  }
}

具体执行顺序：

  1. 发现(0,0)，count=1，入队[(0,0)]
    • 处理(0,0)：
      • 沉没自己
      • 将(1,0)和(0,1)加入队列[(1,0),(0,1)]
  2. 处理(1,0)：
    • 沉没自己
    • (2,0)是水，(0,0)已沉没，(1,1)是水
    • 队列剩下[(0,1)]
  3. 处理(0,1)：
    • 沉没自己
    • (1,1)是水，其他方向无效
  4. 队列空，继续扫描…
    • 发现(1,2)，count=2，开始新的BFS

4. 关键理解突破点

💡 DFS的递归栈是什么？

  • 就像你玩RPG游戏时的任务列表：
    • 接到主线任务（第一次调用dfs）
    • 遇到支线任务（递归调用）就先做支线
    • 支线做完才继续主线

💡 BFS的队列如何工作？

  • 就像银行取号机：
    • 先取号的人先办理（先进先出）
    • 新来的人排队在末尾
    • 柜员永远处理当前最前面的号码

5. 常见误区纠正

误区1：DFS一定比BFS快

  • 不一定！DFS可能绕远路，BFS能找到最短路径

误区2：BFS必须用队列

  • 正确！这是BFS的核心特征

误区3：递归就是DFS

  • 不完全对，DFS可以用栈+循环实现，递归只是常见实现方式

6. 终极理解技巧

自己动手在纸上画：

  1. 画一个5x5的网格，随机放一些’1’
  2. 用不同颜色笔模拟DFS和BFS的访问顺序
  3. 对比两者的访问顺序差异

记住这个核心：

  • DFS：一条路走到黑 → 用递归/栈 → 适合找是否存在路径
  • BFS：层层推进 → 用队列 → 适合找最短路径

经过这样的生活化比喻和逐步拆解，现在应该对DFS和BFS有了更清晰的认识了吧？如果还有疑问，可以试着用这些方法分析更简单的2x2网格，很快就能掌握精髓！