岛屿数量问题解析：DFS、BFS与并查集实现

1. 岛屿数量问题解析岛屿数量是计算机算法中一个经典的图论问题也是各大科技公司面试中的高频考题。我第一次遇到这个问题是在准备算法面试时当时就被它简洁描述背后隐藏的巧妙解法所吸引。这个问题看似简单却能考察面试者对深度优先搜索DFS和广度优先搜索BFS等基础算法的掌握程度。问题的标准描述是给定一个由1(陆地)和0(水)组成的二维网格计算网格中岛屿的数量。岛屿被定义为被水包围的、且通过水平或垂直方向上相邻的陆地连接形成的区域。你可以假设网格的四个边均被水包围。2. 问题分析与解法思路2.1 问题理解与建模首先我们需要明确几个关键点岛屿是由相邻的1组成的区域相邻指的是水平或垂直方向对角线不算单独的1也可以构成一个岛屿我们需要统计这样的独立区域有多少个这个问题可以建模为图论中的连通分量问题每个1可以看作图中的一个节点相邻的1之间存在边。我们的目标就是计算这个图中有多少个连通分量。2.2 基本解法思路最直观的解法是遍历整个网格当遇到一个1时岛屿计数加1通过DFS或BFS将所有与之相连的1标记为已访问可以改为0继续遍历直到网格结束这种方法确保每个岛屿只被计数一次因为发现岛屿后会立即淹没整个岛屿。3. 深度优先搜索(DFS)实现3.1 DFS算法详解DFS是解决这个问题的自然选择因为它可以深入探索一个岛屿的所有部分。下面是详细的实现步骤def numIslands(grid): if not grid: return 0 count 0 rows, cols len(grid), len(grid[0]) for i in range(rows): for j in range(cols): if grid[i][j] 1: count 1 dfs(grid, i, j, rows, cols) return count def dfs(grid, i, j, rows, cols): if i 0 or j 0 or i rows or j cols or grid[i][j] ! 1: return grid[i][j] 0 # 标记为已访问 # 递归访问四个方向 dfs(grid, i1, j, rows, cols) dfs(grid, i-1, j, rows, cols) dfs(grid, i, j1, rows, cols) dfs(grid, i, j-1, rows, cols)3.2 DFS的时间复杂度分析时间复杂度O(M×N)其中M是行数N是列数。因为我们需要遍历整个网格每个单元格最多被访问两次一次在主循环一次在DFS。空间复杂度最坏情况下O(M×N)当整个网格都是陆地时递归深度可能达到M×N。4. 广度优先搜索(BFS)实现4.1 BFS算法详解BFS是另一种可行的解法它使用队列来逐层探索相邻的陆地from collections import deque def numIslands(grid): if not grid: return 0 count 0 rows, cols len(grid), len(grid[0]) for i in range(rows): for j in range(cols): if grid[i][j] 1: count 1 grid[i][j] 0 # 标记为已访问 queue deque() queue.append((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 rows and 0 ny cols and grid[nx][ny] 1: grid[nx][ny] 0 queue.append((nx, ny)) return count4.2 BFS与DFS的比较BFS使用队列DFS使用递归或显式栈BFS的空间复杂度在最坏情况下可能比DFS更好特别是当岛屿形状为宽而短时DFS的代码通常更简洁但可能有栈溢出的风险对于非常大的网格实际应用中两者性能差异不大选择取决于具体场景和个人偏好5. 并查集(Union-Find)解法5.1 并查集原理并查集是一种树型的数据结构用于处理不相交集合的合并及查询问题。它支持两种操作Find确定元素属于哪个子集Union将两个子集合并成一个集合5.2 并查集实现岛屿计数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 i in range(rows): for j in range(cols): if grid[i][j] 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 elif self.rank[rootx] self.rank[rooty]: self.parent[rootx] rooty else: self.parent[rooty] rootx self.rank[rootx] 1 self.count - 1 def numIslands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind(grid) for i in range(rows): for j in range(cols): if grid[i][j] 1: grid[i][j] 0 index i * cols j if i 0 and grid[i-1][j] 1: uf.union(index, (i-1)*cols j) if i rows-1 and grid[i1][j] 1: uf.union(index, (i1)*cols j) if j 0 and grid[i][j-1] 1: uf.union(index, i*cols j-1) if j cols-1 and grid[i][j1] 1: uf.union(index, i*cols j1) return uf.count5.3 并查集的优缺点优点适合动态处理连通性问题可以逐步添加新的连接关系缺点实现相对复杂对于静态问题如岛屿计数可能不如DFS/BFS高效6. 实际应用与变种问题6.1 实际应用场景岛屿数量问题不仅仅是算法题它在实际中有很多应用图像处理中的连通区域分析地图服务中的陆地面积计算医学图像中的病灶区域识别电路板中的连通性检查6.2 常见变种问题统计岛屿的最大面积计算岛屿的周长不同形状的岛屿允许对角线连接动态岛屿问题网格会随时间变化三维岛屿问题扩展到三维网格7. 性能优化与注意事项7.1 优化技巧对于非常大的网格可以考虑迭代式DFS避免递归栈溢出并行处理将网格分块分别处理后再合并结果使用位运算优化存储如果网格是二进制的7.2 常见错误与调试忘记处理空输入的情况数组越界访问特别是在递归/循环中错误地标记已访问的单元格忽略对角线是否应该被视为相邻的条件在并查集实现中路径压缩或按秩合并的实现错误提示在面试中建议先讨论最简单的DFS/BFS解法然后再讨论可能的优化和变种。清晰地解释你的思路比直接写出完美代码更重要。8. 代码测试与验证8.1 测试用例设计好的测试用例应该包括空网格全为0的网格全为1的网格常规情况混合0和1边缘情况最小网格1x1特殊形状的岛屿如十字形、L形等8.2 示例测试def test_numIslands(): # 测试空网格 assert numIslands([]) 0 # 测试全水网格 assert numIslands([[0,0],[0,0]]) 0 # 测试全陆地网格 assert numIslands([[1,1],[1,1]]) 1 # 测试常规情况 grid1 [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ] assert numIslands(grid1) 3 # 测试单个单元格 assert numIslands([[1]]) 1 assert numIslands([[0]]) 0 print(所有测试用例通过!)9. 语言特定实现注意事项9.1 Python实现要点注意列表的边界检查Python的递归深度限制默认1000对于大网格可能需要改为迭代实现使用deque实现BFS比列表更高效9.2 Java/C实现差异需要显式管理内存和数据结构递归实现可能更高效取决于编译器优化多维数组的访问语法不同10. 扩展思考与进阶学习岛屿数量问题可以引发出许多有趣的扩展思考如何实时维护岛屿数量当网格动态变化时如何处理海量数据网格无法完全放入内存如何分布式计算岛屿数量如何可视化算法执行过程对于想要深入学习的同学我推荐以下方向图论中的连通性问题并查集数据结构的其他应用并行算法设计图像处理中的连通组件标记算法在实际编程中遇到类似问题时最重要的是先明确问题定义和边界条件然后选择合适的数据结构和算法。岛屿问题教会我们看似复杂的问题往往有简洁优雅的解决方案关键在于如何将问题抽象和建模。