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

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(r1, c) dfs(r-1, c) dfs(r, c1) 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 count2.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.count3. 算法优化与变种问题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) # 对角线岛屿 ]5. 实际应用场景岛屿数量问题不仅是算法题在以下领域有实际应用图像处理中的连通区域分析地图服务中的地块划分电路板上的元件分组社交网络中的社群发现医学影像中的病灶区域识别理解这类问题的解法有助于处理更复杂的实际场景比如动态变化的网格环境三维空间的连通域分析带权重的区域划分问题