LeetCode 200. 岛屿数量：DFS、BFS 与并查集三种解法

题目与本质

LeetCode 200「岛屿数量」：给定 m × n 的二维网格，'1' 是陆地、'0' 是水，陆地沿上下左右四个方向相连构成岛屿（斜向相邻不算），求岛屿个数。

剥掉场景外壳，这题的本质是数连通分量（连通分量：图里互相可达、与外界不可达的极大连通块）。把每个格子看成节点，相邻的陆地格子之间连一条边，网格就是一张图，「岛屿个数」就是「图中连通分量的个数」。想通这一层，DFS、BFS、并查集三种解法只是「遍历同一张图」的不同姿势。

举个小例子：3×3 网格里第一行是 1 1 0，第三行第三列是 1，其余都是 0，答案是 2 座岛——左上角两格连成一座，右下角一格自成一座；右下角与左上角只隔一条对角线，不算连通。所有解法都必须先认下这条规则：连通只沿上下左右。

解法一：DFS 沉岛

最直观的写法：扫描网格，遇到 '1' 就把计数器加一，同时从这里出发做深度优先搜索（DFS：一条路走到黑、走不通再回溯），把整块连通陆地全部改成 '0'——俗称「沉岛」。沉岛保证同一块陆地只触发一次计数。

def numIslands(grid):
    m, n = len(grid), len(grid[0])

    def sink(i, j):
        if 0 <= i < m and 0 <= j < n and grid[i][j] == '1':
            grid[i][j] = '0'                 # 沉岛，避免重复访问
            sink(i + 1, j)
            sink(i - 1, j)
            sink(i, j + 1)
            sink(i, j - 1)

    count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                sink(i, j)
    return count

十几行搞定，是三解法中最短的。如果不允许改输入，把 grid[i][j] = '0' 换成往 visited 集合登记、判断处同步检查即可，逻辑完全不变。代价在递归深度：最坏情况下（整张网格都是陆地）递归深度达到 mn 量级，Python 默认递归上限只有一千，大网格会直接爆栈。

解法二：BFS 逐层扩散

把递归换成广度优先搜索（BFS：借助队列逐层向外扩散）：发现 '1' 就入队并标记，随后循环出队、把四邻中的陆地入队标记。递归深度问题不复存在，大网格场景更稳。

from collections import deque

def numIslands(grid):
    m, n = len(grid), len(grid[0])
    count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] != '1':
                continue
            count += 1
            grid[i][j] = '0'
            queue = deque([(i, j)])
            while queue:
                x, y = queue.popleft()
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
                        grid[nx][ny] = '0'   # 入队前就标记，防止重复入队
                        queue.append((nx, ny))
    return count

一个关键细节：入队时就标记，而不是出队时再标记。后者会让同一格子被多个邻居重复塞进队列，耗时与内存都翻几倍。

解法三：并查集

并查集（Union-Find）维护「谁与谁同属一个集合」：每个元素记一个父指针，find 沿父指针找到集合代表元，union 把两个集合合并成一个。配合路径压缩——查找途中把沿途节点直接挂到更靠近根的位置——单次操作的均摊代价近似常数。

用于本题：每个陆地格子初始自成集合，变量 land 等于陆地总数；扫描每块陆地，只看它的右邻与下邻（两个方向即可覆盖全部相邻关系），是陆地就 union；每次合并实际发生（两个格子原本不在同一集合）就把 land 减一。最终 land 就是岛屿数。「陆地数减成功合并次数」为什么对？每块陆地开局各算一座岛；每次成功合并都把两座岛并成一座，岛屿数恰好减一；合并失败说明两块地早已同岛，不改变计数。

def numIslands(grid):
    m, n = len(grid), len(grid[0])
    parent = list(range(m * n))
    land = sum(row.count('1') for row in grid)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]    # 路径压缩：隔代挂根
            x = parent[x]
        return x

    def union(a, b):
        nonlocal land
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
            land -= 1                        # 合并成功，分量数减一

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                if j + 1 < n and grid[i][j + 1] == '1':
                    union(i * n + j, i * n + j + 1)
                if i + 1 < m and grid[i + 1][j] == '1':
                    union(i * n + j, (i + 1) * n + j)
    return land

并查集的独特价值在于不要求一次性拿到整张图：格子可以流式到来，来一对合并一对，随时查询当前分量数——这是 DFS/BFS 做不到的，也是「陆续加陆地」的动态连通场景（LeetCode 305）的标准工具。

三解法对比

三种解法的时间都由「每个格子被触碰常数次」保证：DFS/BFS 靠标记防重访，并查集靠合并防重算。这也是所有网格遍历题的共同骨架——先保证不重复处理同一个格子，再谈别的。

易错点

• 能否修改原数组：沉岛直接改输入，工程上未必允许；不允许就用等大小的 visited 矩阵标记，别静默改调用方的数据。
• 重复计数：计数只发生在扫描入口处，标记必须在触发时立即做；BFS 里「出队才标记」是重复入队的经典 bug。
• 方向遗漏：四方向数组写全，斜向不算相邻；并查集只扫右、下两方向是刻意的减半优化，漏成只扫一个方向就错了。

延伸与小结

LeetCode 695「岛屿的最大面积」只需把触发时的计数器换成面积累加——「这块连通块有几个格子」，一行改动。掌握「网格即图、数的是连通分量」这个抽象，200 岛屿数量、695 最大面积、130 被围绕的区域就是同一族题。