岛屿数量怎样用 DFS 或 BFS 求？

简答

给一个由 '1'（陆地）和 '0'（水）组成的二维网格，上下左右相连的陆地算一座岛，斜着挨着的不算，问一共有几座岛。这是 LeetCode 200 题。

做法是从左上角开始一格一格扫。碰到一块陆地，而且之前没访问过，说明发现了一座新岛，计数加 1。接着从这块陆地出发，把和它相连的所有陆地都找出来、标记成已访问，这一步叫“淹没”这座岛。扫完整个网格，计数就是答案。

找相连的陆地有两种方式。DFS 是一条路走到底，用递归写最短；BFS 是一圈一圈往外扩，用队列。两者都只是遍历顺序不同，结果一样。每个格子最多被访问一次，所以时间是 O(mn)。

要注意，递归 DFS 的深度可能和陆地格子数一样多，网格很大、全是陆地时会栈溢出，这时用 BFS 或者显式栈更稳。另外，直接把访问过的陆地改成 '0' 能省掉一个 visited 数组，但会修改调用者传进来的数据，要先说清楚能不能改。

DFS 和 BFS 两种写法

下面两个函数用同一个网格，都用一个 visited 数组记录访问过的格子，不修改输入。

JavaScript

const DIRECTIONS = [[1, 0], [-1, 0], [0, 1], [0, -1]];

function numIslandsDFS(grid) {
  const rows = grid.length;
  const cols = rows ? grid[0].length : 0;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));

  function sink(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (grid[r][c] !== '1' || visited[r][c]) return;
    visited[r][c] = true;
    for (const [dr, dc] of DIRECTIONS) sink(r + dr, c + dc);
  }

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

function numIslandsBFS(grid) {
  const rows = grid.length;
  const cols = rows ? grid[0].length : 0;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  let count = 0;

  for (let r = 0; r < rows; r += 1) {
    for (let c = 0; c < cols; c += 1) {
      if (grid[r][c] !== '1' || visited[r][c]) continue;
      count += 1;
      // 入队时就标记，避免同一个格子被不同邻居重复放进队列。
      visited[r][c] = true;
      const queue = [[r, c]];
      for (let head = 0; head < queue.length; head += 1) {
        const [cr, cc] = queue[head];
        for (const [dr, dc] of DIRECTIONS) {
          const nr = cr + dr;
          const nc = cc + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
          if (grid[nr][nc] !== '1' || visited[nr][nc]) continue;
          visited[nr][nc] = true;
          queue.push([nr, nc]);
        }
      }
    }
  }
  return count;
}

const grid = [
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1'],
];

console.log(numIslandsDFS(grid)); // 3
console.log(numIslandsBFS(grid)); // 3
console.log(numIslandsDFS([['1', '0'], ['0', '1']])); // 2
console.log(numIslandsBFS([])); // 0

grid 是 LeetCode 题面的第二个例子：左上角四块连成一座，中间一块单独一座，右下角两块连成一座，一共 3 座。[['1', '0'], ['0', '1']] 的两块陆地是斜着挨着的，题目只算上下左右，所以是 2 座。

sink 开头为什么先判断越界和是否访问过？这样调用的地方就不用管邻居合不合法，四个方向直接递归下去，不合法的在下一层直接返回。已访问的判断也很关键，没有它，两块相邻的陆地会互相递归，永远停不下来。

BFS 为什么要在入队时标记，而不是出队时？一个格子可能同时是好几个已入队格子的邻居。如果出队时才标记，它会被放进队列好几次，虽然结果还是对的，但做了重复的工作。

队列为什么用 head 下标，而不是 queue.shift()？shift 要把后面的元素全部往前挪，大网格上会变慢；用下标往后走，每次取出都是 O(1)。

递归 DFS 什么时候会出问题

递归每深入一层，调用栈就多一帧。LeetCode 这题的网格最大是 300 × 300，一共 9 万个格子，如果全是陆地，sink 的递归深度可能达到几万层。用 Node.js 22.23 实测，把上面的 sink 用在 300 × 300、全是陆地的网格上，会抛出 RangeError: Maximum call stack size exceeded。改成 BFS，或者用数组当栈自己压入弹出，就不受这个限制。显式栈的写法见《怎样用显式栈实现树的前序遍历？》。

常见追问

并查集也能做这题，什么时候用它？

网格固定不变时，DFS 和 BFS 更直接。如果陆地是一块一块加进来的，每加一块都要回答“现在有几座岛”，每次都重新遍历太慢，用并查集只需要把新陆地和相邻陆地合并，见《并查集怎样实现？适合解决什么问题？》。

怎样求最大岛屿的面积？

思路一样，只是 sink 不再只做标记，而是返回这座岛的格子数：当前格子算 1，再加上四个方向递归返回的数。扫描时用一个变量记录最大值。