岛屿数量问题为什么是图遍历？DFS、BFS、并查集怎么选？

简化版

岛屿数量把二维网格里的每个陆地格子看成图节点，上下左右相邻就是边。遍历网格时，每遇到一个未访问陆地，就说明发现了一个新连通块，答案加 1，然后用 DFS 或 BFS 把这座岛的所有陆地标记掉。

详细版

核心思路是“数连通块”。对 m * n 的网格逐格扫描，遇到 '1' 且未访问，就从它出发做 DFS/BFS，只沿四个方向走到陆地，把能到达的陆地全部标记为已访问。一次完整遍历对应一座岛，所以启动遍历的次数就是岛屿数量。

DFS 写法可以原地把 '1' 改成 '0'，避免额外 visited 数组；BFS 写法用队列，适合避免递归栈过深。复杂度都是 O(mn)，因为每个格子最多入队或递归访问一次；空间复杂度 DFS 最坏 O(mn) 递归栈，BFS 最坏 O(mn) 队列。

并查集也能做：把每个陆地格子编号为 r * n + c，和右边、下边相邻陆地合并，最后统计集合个数。但面试中如果只是静态网格，DFS/BFS 更直接；如果是动态加陆地、频繁查询连通块，并查集更合适。

完整版教学

一、为什么二维网格可以看成图

很多同学看到矩阵会先想“数组题”，但岛屿数量的本质是图的连通性。每个值为 '1' 的格子是一个节点，如果两个陆地格子上下左右相邻，就在它们之间连一条无向边。题目问“有几座岛”，等价于问“这张无向图有几个连通分量”。

例如下面这个 4 * 5 网格，1 是陆地，0 是水：

左上角三个 1 连成一个分量，中右三个 1 连成一个分量，左下两个 1 连成一个分量，所以答案是 3。这个转换非常重要：一旦能把“相邻关系”抽象成边，就可以直接套图遍历模板。

二、DFS 的做法：遇到一块陆地就沉没整座岛

DFS 的关键动作是“从一个入口递归扩散”。扫描到未访问陆地时，把答案加 1，然后从这个格子开始向四个方向递归，只要下一个格子仍然是陆地，就继续递归。为了避免重复访问，可以把访问过的陆地原地改成 '0'，这也叫“沉岛”。

int numIslands(char[][] grid) {
    int m = grid.length, n = grid[0].length, ans = 0;
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == '1') {
                ans++;
                dfs(grid, r, c);
            }
        }
    }
    return ans;
}

void dfs(char[][] g, int r, int c) {
    if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] != '1') return;
    g[r][c] = '0';
    dfs(g, r + 1, c);
    dfs(g, r - 1, c);
    dfs(g, r, c + 1);
    dfs(g, r, c - 1);
}

注意答案是在“启动一次 DFS”时加 1，而不是每访问一个陆地加 1。一次 DFS 会覆盖整座岛，如果一座岛有 100 个格子，也只代表 1 个连通块。

三、BFS 的做法：用队列按层扩散

BFS 和 DFS 的访问集合相同，只是遍历顺序不同。BFS 用队列保存待扩散的陆地格子，弹出一个格子后检查四邻域，把未访问陆地入队并标记。它的好处是不用递归，Java 或 Python 里大网格不会因为递归深度爆栈。

发现新岛入口 (r,c)
  -> 入队并标记为水
  -> 队列非空时弹出一个格子
  -> 检查上下左右
  -> 新陆地继续入队
  -> 队列清空，整座岛处理完

如果一个 300 * 300 网格全是陆地，DFS 递归深度最坏可能接近 90000；BFS 队列最坏也可能存很多节点，但不会吃调用栈。面试时可以说：小规模或语言栈足够时 DFS 简洁，大规模生产代码更偏向 BFS 或显式栈。

四、复杂度为什么是 O(mn)

无论 DFS 还是 BFS，每个格子最多发生一次从陆地变成已访问的动作。扫描网格要看 mn 个格子，遍历时每个陆地最多检查四个方向，所以总操作次数不超过常数倍的 mn。

方法	时间复杂度	额外空间	适用场景
DFS 原地修改	O(mn)	最坏 O(mn) 递归栈	写法短，面试最常用
BFS 队列	O(mn)	最坏 O(mn) 队列	避免递归栈过深
并查集	O(mn α(mn))	O(mn)	动态连通性或需要扩展时

这里的 α 是反阿克曼函数，可以近似看成常数。但并查集初始化和编号更繁琐，静态岛屿数量题不必为了炫技而优先使用。

五、四方向、八方向和边界条件

常见默认是上下左右四方向连接，斜对角不算同一座岛。如果题目明确说八方向连接，方向数组才需要加上四个对角方向。方向定义错了，结果会完全不同。

四方向:
    (-1,0)
(0,-1) X (0,1)
    (1,0)

八方向 = 四方向 + 四个对角

边界条件也要先判断：越界、水、已访问都要直接返回。原地改网格时，后续扫描遇到被改成 '0' 的格子不会重复启动遍历；如果面试官要求不能修改输入，就单独维护 boolean[][] visited。

六、并查集为什么也能做

并查集把每个陆地格子看成一个集合，遇到相邻陆地就合并。最终有多少个根节点，就有多少座岛。为了减少重复合并，扫描时只需要检查右边和下边两个方向，因为左边和上边已经在之前处理过。

id(r, c) = r * n + c
if grid[r][c] == '1':
  count++
  if right is land: union(cur, right)
  if down is land: union(cur, down)

如果初始有 8 个陆地格子，合并相邻边成功 5 次，那么岛屿数就是 8 - 5 = 3。这个数字例子能帮助你回答“为什么 union 成功时 count 要减 1”：两个原本不同的连通块被连接成一个，连通块数量自然减少。

七、常见误区与追问

记忆钩子：岛屿数量不是在数格子，而是在数“启动遍历的次数”；一次启动遍历会吃掉一个完整连通块。

误区：每遇到一个陆地都把答案加 1。 只有未访问陆地才能代表一座新岛，已经被 DFS/BFS 标记过的陆地属于之前那座岛。
误区：斜对角也算相连。 默认题意通常只算上下左右四方向，除非题目明确说八方向。
误区：原地修改一定不安全。 面试算法题常允许修改输入；如果业务语义不允许，就用 visited，核心遍历逻辑不变。
追问：递归 DFS 爆栈怎么办？ 可以改成 BFS 队列或手写栈，时间复杂度仍是 O(mn)。
追问：如果陆地是动态加入的怎么办？ 用并查集维护连通块数量，每新增一个陆地先 count++，再和周围陆地 union，成功合并就 count--。
追问：为什么不是最短路径问题？ 题目只关心连通块数量，不关心两个格子之间的最短步数，所以普通遍历足够。

八、加强记忆

这题的记忆主线是“网格转图，岛屿转连通块”。扫描网格时，未访问陆地是新连通块入口，答案加 1；DFS/BFS 负责把入口所在连通块全部标记掉。复杂度是 O(mn)，因为每个格子最多被处理一次。若题目变成动态加陆地，就从遍历思路切到并查集思路，用集合合并维护岛屿数量。

简化版

详细版