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

发布时间：2026/11/2 21:46:51
岛屿数量问题：DFS、BFS与并查集算法解析

1. 岛屿数量问题解析

今天我们来聊聊这个经典的算法问题——岛屿数量。第一次看到这个题目时，你可能觉得它很简单，但深入思考后会发现其中蕴含着不少值得探讨的细节。这个问题不仅常见于技术面试，在实际应用中也有很多场景，比如图像处理中的连通区域分析、地理信息系统中的岛屿识别等。

2. 问题定义与理解

2.1 问题描述

给定一个由'1'(陆地)和'0'(水)组成的二维网格，计算网格中岛屿的数量。岛屿被水包围，并且通过水平或垂直方向上相邻的陆地连接形成。你可以假设网格的四个边都被水包围。

示例输入：

[ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ]

输出：3

2.2 关键概念解析

理解这个问题需要明确几个关键点：

  1. 网格表示：通常用二维数组表示，每个元素要么是'1'要么是'0'
  2. 相邻定义：仅考虑上下左右四个方向，不考虑对角线
  3. 岛屿定义：一组相邻的'1'组成一个岛屿

3. 解决方案设计

3.1 基本思路

解决这个问题的核心思路是遍历整个网格，当遇到一个'1'时，就找到了一个岛屿，然后需要把这个岛屿的所有相邻'1'都标记为已访问，避免重复计数。

3.2 算法选择

主要有两种经典算法可以解决这个问题：

  1. 深度优先搜索(DFS)
  2. 广度优先搜索(BFS)

两种方法的时间复杂度都是O(M×N)，其中M和N分别是网格的行数和列数。

4. 深度优先搜索实现

4.1 算法步骤

  1. 遍历网格中的每个单元格
  2. 当遇到'1'时，岛屿计数加1
  3. 从这个'1'开始进行DFS，将所有相连的'1'标记为'0'(表示已访问)
  4. 继续遍历直到网格结束

4.2 代码实现

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

4.3 复杂度分析

  • 时间复杂度：O(M×N)，每个单元格最多被访问两次
  • 空间复杂度：O(M×N)，最坏情况下递归栈的深度

5. 广度优先搜索实现

5.1 算法步骤

  1. 遍历网格中的每个单元格
  2. 当遇到'1'时，岛屿计数加1
  3. 初始化一个队列，将当前'1'的位置加入队列
  4. 从队列中取出位置，检查其四个邻居
  5. 如果是'1'，则标记为'0'并加入队列
  6. 重复直到队列为空

5.2 代码实现

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 grid[r][c] = '0' queue = deque([(r, c)]) 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': grid[nr][nc] = '0' queue.append((nr, nc)) return count

5.3 复杂度分析

  • 时间复杂度：O(M×N)
  • 空间复杂度：O(min(M,N))，队列的最大长度

6. 并查集解决方案

6.1 并查集简介

并查集(Disjoint Set Union)是一种数据结构，用于处理不相交集合的合并与查询问题。它支持两种操作：

  1. Find：查找元素所属集合
  2. Union：合并两个集合

6.2 算法思路

  1. 初始化并查集，每个'1'的单元格都是一个独立集合
  2. 遍历网格，对于每个'1'，检查其右侧和下侧的邻居
  3. 如果邻居也是'1'，则合并这两个集合
  4. 最后统计独立集合的数量

6.3 代码实现

class UnionFind: def __init__(self, grid): rows, cols = len(grid), len(grid[0]) self.parent = [i for i in range(rows * cols)] self.count = sum(grid[r][c] == '1' for r in range(rows) for c in range(cols)) 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: self.parent[rootx] = rooty 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': index = r * cols + c if r + 1 < rows and grid[r+1][c] == '1': uf.union(index, (r+1)*cols + c) if c + 1 < cols and grid[r][c+1] == '1': uf.union(index, r*cols + c+1) return uf.count

6.4 复杂度分析

  • 时间复杂度：O(M×N×α(M×N))，其中α是反阿克曼函数，增长极慢
  • 空间复杂度：O(M×N)

7. 性能比较与选择

7.1 三种方法对比

方法时间复杂度空间复杂度适用场景
DFSO(M×N)O(M×N)网格较小，递归深度可控
BFSO(M×N)O(min(M,N))网格较大，避免递归栈溢出
并查集O(M×N×α(M×N))O(M×N)需要动态处理岛屿合并

7.2 选择建议

  1. 面试场景：推荐DFS或BFS，代码简洁易懂
  2. 大规模网格：BFS更优，避免递归栈溢出
  3. 动态岛屿合并：并查集是唯一选择

8. 常见问题与优化

8.1 边界条件处理

  • 空输入：直接返回0
  • 单行或单列网格：需要特殊处理吗？不需要，通用解法适用
  • 全'0'或全'1'的情况：需要正确处理

8.2 优化技巧

  1. 原地修改：直接修改输入网格来标记访问状态
  2. 提前终止：如果已经访问所有'1'，可以提前结束
  3. 并行处理：对于极大网格，可以考虑并行算法

8.3 常见错误

  1. 忘记标记已访问的单元格，导致无限循环
  2. 错误处理网格边界，导致数组越界
  3. 对角线相邻误认为属于同一岛屿

9. 实际应用场景

9.1 图像处理

在图像处理中，岛屿数量问题可以用于：

  • 连通区域分析
  • 目标检测
  • 图像分割

9.2 地理信息系统

  • 真实岛屿计数
  • 湖泊识别
  • 地块划分

9.3 社交网络

  • 寻找独立用户群体
  • 社区发现
  • 网络连通性分析

10. 变种问题

10.1 最大岛屿面积

不仅计算岛屿数量，还要找出最大岛屿的面积

10.2 封闭岛屿数量

统计完全被水('0')包围的岛屿数量

10.3 不同形状岛屿

识别并统计不同形状的岛屿数量

11. 个人实现心得

在实际编码实现时，我有几点经验分享：

  1. 优先考虑DFS实现，代码通常更简洁
  2. 使用BFS时，注意队列的实现方式，Python中deque比list效率更高
  3. 并查集的路径压缩优化能显著提升性能
  4. 测试时要考虑极端情况，如全'1'、全'0'、单行、单列等
  5. 在标记访问状态时，可以直接修改输入数组，避免额外空间开销