当前位置：首页 > news >正文

LeetCode岛屿数量问题：DFS/BFS/并查集解法详解

news 2026/8/10 3:24:03

1. 问题概述与核心思路

LeetCode 200题"岛屿数量"是算法面试中的经典问题，主要考察图的遍历和连通域分析能力。题目给定一个由'1'（陆地）和'0'（水）组成的二维网格，要求计算其中岛屿的数量。岛屿被定义为水平或垂直方向上相邻的陆地组成的区域。

这个问题的关键在于理解"相邻"的定义——只有上下左右四个方向的连接才算相邻，对角线方向的连接不被考虑。例如在以下3x3网格中：

1 1 0 0 1 0 0 0 1

存在两个岛屿：左上角的3个'1'组成一个岛屿，右下角的单个'1'是另一个岛屿。

2. 解法分析与实现细节

2.1 深度优先搜索(DFS)解法

DFS是最直观的解决方法，时间复杂度O(M×N)，空间复杂度O(M×N)（最坏情况下递归栈的深度）：

def numIslands(grid): if not grid: return 0 count = 0 rows, cols = len(grid), len(grid[0]) def dfs(r, c): if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1': return grid[r][c] = '0' # 标记为已访问 dfs(r+1, c) dfs(r-1, c) dfs(r, c+1) dfs(r, c-1) for r in range(rows): for c in range(cols): if grid[r][c] == '1': count += 1 dfs(r, c) return count

注意：这里直接修改了输入网格，如果不允许修改原数组，需要额外使用visited矩阵记录访问状态。

2.2 广度优先搜索(BFS)解法

BFS使用队列实现，同样时间复杂度O(M×N)，空间复杂度O(min(M,N))：

from collections import deque def numIslands(grid): if not grid: return 0 count = 0 rows, cols = len(grid), len(grid[0]) for r in range(rows): for c in range(cols): if grid[r][c] == '1': count += 1 queue = deque([(r, c)]) grid[r][c] = '0' while queue: row, col = queue.popleft() for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc = row + dr, col + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1': queue.append((nr, nc)) grid[nr][nc] = '0' return count

2.3 并查集(Union-Find)解法

并查集适合处理动态连通性问题，时间复杂度O(M×N×α(M×N))，其中α是反阿克曼函数：

class UnionFind: def __init__(self, grid): rows, cols = len(grid), len(grid[0]) self.count = 0 self.parent = [i for i in range(rows * cols)] self.rank = [0] * (rows * cols) for r in range(rows): for c in range(cols): if grid[r][c] == '1': self.count += 1 def find(self, i): if self.parent[i] != i: self.parent[i] = self.find(self.parent[i]) return self.parent[i] def union(self, x, y): rootx = self.find(x) rooty = self.find(y) if rootx != rooty: if self.rank[rootx] > self.rank[rooty]: self.parent[rooty] = rootx else: self.parent[rootx] = rooty if self.rank[rootx] == self.rank[rooty]: self.rank[rooty] += 1 self.count -= 1 def numIslands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) uf = UnionFind(grid) for r in range(rows): for c in range(cols): if grid[r][c] == '1': grid[r][c] = '0' for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc = r + dr, c + dc if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1': uf.union(r * cols + c, nr * cols + nc) return uf.count

3. 算法优化与变种问题

3.1 空间复杂度优化

对于DFS/BFS解法，可以通过以下方式优化空间：

使用原矩阵标记访问状态（如将'1'改为'0'）
使用位运算压缩状态信息
BFS中使用双端队列优化

3.2 常见变种问题

统计岛屿的最大面积
统计封闭岛屿数量（岛屿不接触网格边缘）
统计不同形状岛屿的数量
允许对角线连接的岛屿数量统计
动态岛屿问题（网格会随时间变化）

4. 面试技巧与注意事项

明确问题边界条件：
- 空网格处理
- 全'0'或全'1'的情况
- 网格只有一行或一列的情况
代码实现细节：
- 使用方向数组简化相邻节点访问
- 避免重复创建临时变量
- 注意Python中列表的浅拷贝问题
复杂度分析要点：
- 每个节点最多被访问一次
- 递归深度的影响因素
- 并查集路径压缩的效率
测试用例设计：

test_cases = [ ([], 0), # 空网格 ([["0"]], 0), # 单个水单元格 ([["1"]], 1), # 单个陆地单元格 ([["1","1","1"],["0","0","0"],["1","1","1"]], 2), # 两行岛屿 ([["1","0","1"],["0","1","0"],["1","0","1"]], 5) # 对角线岛屿 ]