DFS、BFS与并查集：三种算法解决岛屿问题实战指南

1. 项目概述：从“岛屿”到“连通域”的算法世界

如果你刷过LeetCode，或者准备过任何一场技术面试，那么“岛屿问题”对你来说绝对不是一个陌生的名字。它就像算法世界里的“Hello World”，看似简单，却蕴含着图论、搜索和并查集等核心思想的精髓。我第一次系统性地解决这类问题，是在准备一次关键的算法岗面试时，当时被各种变体题目搞得晕头转向，直到我静下心来，把DFS（深度优先搜索）、BFS（广度优先搜索）和UF（并查集）这三种武器彻底拆解清楚，才真正打通了任督二脉。

简单来说，“岛屿问题”是一个经典的建模问题：在一个由‘1’（陆地）和‘0’（水）组成的二维网格中，计算“岛屿”的数量。其中，一个“岛屿”被定义为由相邻的陆地水平或垂直连接而成，且被水包围。这里的“相邻”通常指上下左右四个方向。这个模型可以轻松地映射到无数现实场景：图像处理中连通白色像素区域的数量、社交网络中独立社群的数量、电路板中金属连通的区域，甚至是疫情传播中隔离区的划分。掌握了解决它的方法，你就掌握了一把打开许多复杂问题的钥匙。

今天，我们就抛开那些枯燥的教科书定义，从一个一线开发者的视角，深入聊聊如何用DFS、BFS和UF这三种截然不同的思路，优雅地“淹没”这些岛屿。我会带你看到每种方法背后的设计哲学、代码实现中那些教科书里不会写的“坑”，以及在不同约束条件下该如何做出最明智的选择。无论你是正在啃《算法导论》的学生，还是需要快速解决一个实际连通性问题的工程师，这篇文章都能给你提供可以直接“抄作业”的实战方案。

2. 核心思路拆解：三种武器的哲学与适用场景

在动手写代码之前，搞清楚每种方法的“心法”至关重要。选择哪种算法，往往取决于你对问题规模、数据特性和额外需求的理解。

2.1 DFS：递归的优雅与栈溢出的风险

深度优先搜索的核心思想是“一条道走到黑，不行再回头”。对于岛屿问题，当我们遇到一块陆地（‘1’）时，DFS的策略是立刻以它为起点，向一个方向（比如先向右）深入探索，标记所有能到达的陆地，直到被水（‘0’）或边界包围，然后回溯到上一个岔路口，换一个方向继续探索。

为什么选择DFS？它的代码实现极其简洁，递归函数本身就能完美地表达“探索-标记-返回”这个过程，逻辑清晰，非常适合快速原型开发和面试场景。在网格不算特别大（比如几百乘几百），且递归深度可控的情况下，DFS是首选。

它的致命弱点是什么？递归。这是DFS的阿喀琉斯之踵。当网格非常大，或者岛屿的形状极其狭长（想象一个蛇形岛屿），递归深度可能轻易达到几千甚至上万层，直接导致栈溢出（Stack Overflow）。这是生产环境中必须严肃对待的问题。

注意：即使在允许递归的竞赛或面试中，也最好主动提及递归深度的风险，并说明可以用栈模拟递归（迭代DFS）来规避，这能体现你的工程思维。

2.2 BFS：层序的稳健与内存的挑战

广度优先搜索的思想是“稳扎稳打，层层推进”。从一块陆地出发，我们不急着往深处走，而是先把紧挨着它的所有邻居陆地（同一层）都访问并标记了，然后再以这些邻居为新的起点，去访问它们的邻居。

为什么选择BFS？BFS通常使用队列（Queue）实现，是迭代过程，完全避免了递归深度限制的问题，因此在处理超大网格时更加稳健。它天然地保证了“由近及远”的访问顺序，这个特性在某些变体问题中很有用，比如计算岛屿的“面积”或“最短路径到边界”。

它的挑战在哪里？内存。在最坏情况下，队列中可能需要同时存储几乎一整层网格节点。对于一个N x N的网格，如果全是陆地，队列的峰值大小可以达到O(N)（对于“蛇形”岛屿）甚至O(N^2)（对于“肥胖”岛屿）。虽然这通常比递归栈溢出要好处理，但在极端内存受限的环境下仍需考量。

2.3 UF：并查集的降维打击与初始化成本

并查集是一种专门用于处理动态连通性问题的数据结构。它的思路不是去“搜索”或“遍历”，而是“合并”与“查询”。我们将网格中的每个‘1’都看作一个独立的集合，然后遍历网格，如果发现两个相邻的‘1’，就将它们所在的集合合并。最终，剩余独立集合的个数，就是岛屿的数量。

为什么选择UF？这是一种“降维打击”。当问题不仅仅是计数，后续还需要频繁、动态地查询两个位置是否属于同一个岛屿，或者动态添加陆地时，并查集的优势是压倒性的。它的find和union操作经过路径压缩和按秩合并优化后，时间复杂度接近常数级O(α(n))，效率极高。

它的代价是什么？初始化成本。并查集需要为每个陆地位置创建一个集合元素，初始化操作是O(M*N)。对于单纯的“一次计数”问题，它的前期开销可能比DFS/BFS的简单遍历还要大。所以，它强在动态场景，而非静态的一次性计算。

为了更直观地对比，我整理了一个决策表：

3. 核心细节解析与实操要点

理解了宏观思路，我们深入到代码层面。这里有几个无论用哪种方法都必须处理的通用细节，它们往往是bug的高发区。

3.1 网格的表示与访问

我们通常用一个二维字符数组grid[][]或整型数组来表示地图。grid[i][j]表示第 i 行、第 j 列。这里第一个易错点是行列顺序和边界检查。

# 正确的边界检查 def in_area(grid, i, j): return 0 <= i < len(grid) and 0 <= j < len(grid[0])

我见过不少新手写出j < len(grid)的错误，这在对非正方形网格操作时会直接导致数组越界。一个记忆技巧：len(grid)是“行数”（有多少个一维数组），len(grid[0])是“列数”（第一个一维数组的长度）。

3.2 已访问标记：修改原数组 vs. 额外空间

为了避免重复访问同一块陆地，我们必须对访问过的点进行标记。这里有两大流派：

1. “沉岛”派（修改原数据）：直接将访问过的‘1’修改为‘0’或另一个标记字符（如‘2’）。这是最省空间的方法，代码也干净。

   grid[i][j] = ‘0’ # 标记为已访问，相当于“淹没”这块陆地

   前提是：你能修改输入数据。在面试或某些API设计中，输入可能是const（不可变）的，这时此法行不通。

2. “记录”派（额外空间）：维护一个与grid等大的二维布尔数组visited[][]，专门记录访问状态。

   visited = [[False] * n for _ in range(m)] visited[i][j] = True

   优点：不破坏原始数据。缺点：使用了O(M*N)的额外空间。对于纯粹的数量统计问题，通常“沉岛”法是首选。

3.3 方向数组的优雅写法

无论是DFS还是BFS，我们都需要从一个点的四个（有时是八个）方向进行探索。硬编码四个if语句显得冗长。使用“方向数组”是标准且优雅的做法：

# 四方向：上，右，下，左 directions = [(-1, 0), (0, 1), (1, 0), (0, -1)] # 八方向（包含对角线） # directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)] for d in directions: new_i, new_j = i + d[0], j + d[1] if in_area(grid, new_i, new_j) and grid[new_i][new_j] == ‘1’: # 进行递归或入队操作

这种方式将方向控制从业务逻辑中解耦出来，代码更清晰，也更容易修改（比如从四连通改为八连通）。

4. 实操过程与核心环节实现

下面，我们分别用三种方法实现经典的“岛屿数量”问题。我会给出Python版本的核心代码，并附上关键注释和现场思考。

4.1 DFS实现：递归与迭代双版本

递归DFS版本：这是最经典的写法，直观体现了DFS的“深度”特性。

def numIslands_dfs(grid): if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) count = 0 # 方向数组 dirs = [(-1,0), (1,0), (0,-1), (0,1)] def dfs(i, j): # 1. 边界与合法性检查（其实在主循环已检查，这里防御性编程） if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != ‘1’: return # 2. 标记已访问（沉岛） grid[i][j] = ‘0’ # 3. 向四个方向递归探索 for d in dirs: dfs(i + d[0], j + d[1]) # 注意：这里没有“恢复现场”的操作，因为我们是淹没，不是回溯找路径 for i in range(m): for j in range(n): # 发现一块未被淹没的新大陆 if grid[i][j] == ‘1’: count += 1 dfs(i, j) # 调用DFS淹没整个岛屿 return count

踩坑点：dfs函数内部的第一行检查是必须的。虽然主循环调用时(i, j)一定是‘1’，但在递归过程中，new_i, new_j可能越界或已是‘0’。这是递归中常见的防御性编程。

迭代DFS版本（栈模拟）：为了解决递归深度问题，我们可以用栈来手动模拟递归过程。

def numIslands_dfs_iterative(grid): if not grid: return 0 m, n = len(grid), len(grid[0]) count = 0 dirs = [(-1,0), (1,0), (0,-1), (0,1)] for i in range(m): for j in range(n): if grid[i][j] == ‘1’: count += 1 stack = [(i, j)] grid[i][j] = ‘0’ # 入栈即标记 while stack: cur_i, cur_j = stack.pop() # 栈顶弹出，实现深度优先 for d in dirs: ni, nj = cur_i + d[0], cur_j + d[1] if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == ‘1’: stack.append((ni, nj)) grid[ni][nj] = ‘0’ # 关键！入栈前标记，避免重复入栈 return count

实操心得：在迭代DFS中，必须在节点入栈的同时就将其标记为已访问（grid[ni][nj] = ‘0’）。如果等到弹出栈时才标记，会导致同一个节点被不同的邻居多次压入栈中，造成重复计算和栈空间浪费，在密集网格上性能差异巨大。

4.2 BFS实现：队列与层序遍历

BFS的实现与迭代DFS非常相似，只是把栈（Stack）换成了队列（Queue），从而将弹出顺序从“后进先出”改为“先进先出”。

from collections import deque def numIslands_bfs(grid): if not grid: return 0 m, n = len(grid), len(grid[0]) count = 0 dirs = [(-1,0), (1,0), (0,-1), (0,1)] for i in range(m): for j in range(n): if grid[i][j] == ‘1’: count += 1 grid[i][j] = ‘0’ # 标记起点 queue = deque() queue.append((i, j)) while queue: cur_i, cur_j = queue.popleft() # 队列弹出，实现广度优先 for d in dirs: ni, nj = cur_i + d[0], cur_j + d[1] if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == ‘1’: queue.append((ni, nj)) grid[ni][nj] = ‘0’ # 同样，入队即标记 return count

性能小贴士：这里使用collections.deque作为队列，它的popleft()操作是O(1)的，比用列表（list）模拟队列（pop(0)是O(n)）要高效得多。在处理大规模BFS时，这个选择会带来显著的性能提升。

4.3 UF实现：并查集模板与二维映射

并查集的实现稍复杂，我们需要先写好并查集这个“轮子”。这里给出一个带路径压缩和按秩合并（使用大小作为秩）的优化版本。

class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.rank = [1] * n # 用集合大小作为秩 self.count = n # 独立集合个数 def find(self, x): # 路径压缩：在查找过程中将节点直接连到根节点 if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x = self.find(x) root_y = self.find(y) if root_x == root_y: return False # 原本就在一个集合，未发生合并 # 按秩合并：将小树挂到大树下 if self.rank[root_x] < self.rank[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x self.rank[root_x] += self.rank[root_y] self.count -= 1 # 合并后，集合总数减1 return True def get_count(self): return self.count def numIslands_uf(grid): if not grid: return 0 m, n = len(grid), len(grid[0]) # 第一步：初始化，只给陆地编号 uf = UnionFind(m * n) # 最坏情况，全是陆地 water_count = 0 # 遍历第一遍，初始化parent，并数出水域数量 # 注意：这里一种更巧妙的做法是，只把陆地加入UF，水域不计入。 # 但为了保持UF大小固定，我们选择将所有点初始化，最后减去水域对应的集合。 # 实际上，我们可以先数出陆地数量，只为陆地创建UF节点，这样更优。以下是通用写法： for i in range(m): for j in range(n): if grid[i][j] == ‘0’: water_count += 1 # parent已经在__init__中初始化好了 # 第二步：遍历网格，合并相邻陆地 # 只需要向右和向下检查，避免重复合并 dirs = [(1,0), (0,1)] # 只检查右和下 for i in range(m): for j in range(n): if grid[i][j] == ‘0’: continue index = i * n + j # 二维坐标转一维索引 for d in dirs: ni, nj = i + d[0], j + d[1] if ni < m and nj < n and grid[ni][nj] == ‘1’: neighbor_index = ni * n + nj uf.union(index, neighbor_index) # 第三步：计算岛屿数量 # 总集合数 - 水域数量 = 陆地连通域数量 # 但注意，水域在UF里也被视为独立集合，我们需要排除它们。 # 更准确的做法：直接返回 uf.get_count() - water_count # 但前提是水域之间没有进行合并（它们都是‘0’，我们跳过了对他们的union操作）。 # 实际上，由于我们只对‘1’进行union，所有‘0’都自成一个集合，且互不连通。 # 所以岛屿数 = 总集合数 - 水域数 return uf.get_count() - water_count

关键解析：

1. 二维转一维：index = i * n + j是将网格位置映射到并查集数组的标准方法。n是列数，i * n跳过了前面所有行，+ j定位到当前列。
2. 单向合并：在合并相邻陆地时，我们只检查右方和下方的邻居。这是因为union操作是对称的，合并(i,j)和(i+1,j)与合并(i+1,j)和(i,j)效果相同。检查左上两个方向会导致重复的union调用，虽然结果正确，但浪费了性能。这是并查集解决网格问题的经典优化。
3. 水域处理：代码中通过water_count来最终修正数量。另一种更清晰的实现是：初始化时只统计陆地数量land_count，然后在每次成功执行union后，将land_count减1。最终land_count就是岛屿数量。这避免了处理水域集合的麻烦。

5. 常见问题与排查技巧实录

在实际编码和面试中，会遇到一些典型问题。这里我把自己和同事们踩过的坑总结一下。

5.1 栈溢出与递归深度限制

问题现象：在运行递归DFS时，对于大型网格（如1000x1000全为陆地），程序崩溃并报告RecursionError: maximum recursion depth exceeded。

根因分析：Python默认的递归深度限制约为1000层。一个全为陆地的网格，递归深度可能达到M*N量级，远超此限制。

解决方案：

1. 改用迭代DFS/BFS：这是最根本的解决方案。生产代码中，对于可能的大数据，应优先考虑迭代法。
2. 增大递归深度（仅限临时调试）：sys.setrecursionlimit(1000000)。但这只是权宜之计，不能解决深递归导致的函数调用栈内存消耗大的根本问题，且可能掩盖程序逻辑错误。
3. 检查递归终止条件：确保你的递归函数在所有分支上都有正确的终止条件（如遇到‘0’或出界就return），避免无限递归。

5.2 时间复杂度过高与重复计算

问题现象：程序运行时间远超O(M*N)的预期，对于稍大的网格就非常慢。

排查思路：

1. 确认访问标记：这是最常见的原因。你是否在访问一个节点后立即将其标记？在BFS/迭代DFS中，是否在入队/入栈时就标记，而不是在弹出时才标记？后者会导致节点被重复添加和访问。
2. 检查方向数组：确保方向数组定义正确，没有重复或错误的方向导致无效循环。
3. 并查集优化：如果使用UF，确认是否实现了路径压缩和按秩合并。没有优化的UF在链状结构下find操作会退化为O(n)，极大影响性能。确保你的find函数是递归或循环进行路径压缩的。

5.3 计数错误（多算或少算）

问题现象：程序输出的岛屿数量与预期不符。

调试步骤：

1. 小数据测试：用一个3x3或4x4的简单网格进行手动验证。画出网格，手动模拟你的算法。
2. 打印中间状态：在淹没岛屿（或合并集合）的关键步骤后，打印出整个网格的状态（或并查集的parent数组），观察变化是否符合预期。
3. 边界条件：
   • 空输入：你的函数能处理grid = []或grid = [[]]吗？
   • 单行/单列网格：m=1或n=1时，你的循环和边界判断是否仍然正确？
   • 全‘0’或全‘1’：这两种极端情况的结果分别是0和1，你的程序对吗？
4. 方向定义：题目要求是四方向（上下左右）连通还是八方向（包含对角线）连通？这是两个完全不同的问题。务必确认清楚。

5.4 内存占用过大

问题现象：对于超大网格，程序因内存不足（Out of Memory）而崩溃。

分析与优化：

1. BFS队列：在极端情况下（如一个非常“胖”的岛屿），BFS队列可能同时存储大量节点。考虑使用deque并确保及时标记，但内存占用本质上是问题规模决定的。
2. Visited数组：如果你使用了额外的visited数组，尝试改用“沉岛法”直接在原数组上修改，可以节省一个O(M*N)的布尔数组空间。
3. 并查集数组：UF需要parent和rank数组，大小是M*N。如果网格非常稀疏（陆地很少），可以考虑只为陆地节点创建UF元素，使用哈希表来存储映射关系，但这会增加代码复杂度。
4. 算法选择：如果内存是首要瓶颈，递归DFS（栈深度）和BFS（队列宽度）都可能有问题。迭代DFS（用栈）的内存消耗通常介于两者之间，但最坏情况也可能很大。这时需要根据数据特征具体分析。

6. 变体问题实战：从数量到面积、周长与形状

“岛屿数量”只是起点，面试和实际问题中充满了它的变体。掌握核心方法后，我们可以轻松应对。

6.1 岛屿的最大面积

问题：在找到所有岛屿的基础上，返回最大岛屿的面积（即‘1’的个数）。

解法微调：在DFS/BFS淹没一个岛屿的过程中，不再只是默默标记，而是累加访问到的陆地单元格数量。

def maxAreaOfIsland(grid): if not grid: return 0 m, n = len(grid), len(grid[0]) dirs = [(-1,0),(1,0),(0,-1),(0,1)] max_area = 0 def dfs(i, j): if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 1: # 假设输入是整数1 return 0 grid[i][j] = 0 # 淹没 area = 1 # 当前单元格面积 for d in dirs: area += dfs(i+d[0], j+d[1]) # 累加子孙节点的面积 return area for i in range(m): for j in range(n): if grid[i][j] == 1: max_area = max(max_area, dfs(i, j)) return max_area

关键点：递归函数dfs需要返回以(i,j)为根的子树所代表的岛屿面积。这是后序遍历的思想：先处理子节点，再汇总结果。

6.2 岛屿的周长

问题：计算所有岛屿的周长总和。单元格周长的定义是：一个陆地单元格有4条边，每条边如果与水域相邻或者位于网格边界，则这条边计入周长。

解法思路：有两种主流思路：

1. 加法思维：遍历每个陆地单元格，检查其四个方向，如果该方向是边界或者是水，则周长加1。
2. 减法思维：初始周长 = 陆地单元格数 * 4。然后遍历每个陆地单元格，检查其右方和下方（避免重复）是否有相邻陆地，每有一对相邻，总周长减去2（因为两条重合的边不计入周长）。

加法思维更直观，减法思维更高效（只需检查两个方向）。这里给出减法思维的代码：

def islandPerimeter(grid): if not grid: return 0 m, n = len(grid), len(grid[0]) perimeter = 0 for i in range(m): for j in range(n): if grid[i][j] == 1: perimeter += 4 # 只检查右和下，避免重复计算 if i + 1 < m and grid[i+1][j] == 1: perimeter -= 2 # 上下相邻，减去两条边 if j + 1 < n and grid[i][j+1] == 1: perimeter -= 2 # 左右相邻，减去两条边 return perimeter

6.3 统计封闭岛屿数量

问题：封闭岛屿是指一个完全被水域（‘0’）包围的岛屿，即岛屿的所有单元格都不在网格的边界上。

解法思路：核心是先处理边界。我们可以先对位于网格四周边界上的陆地做一次DFS/BFS，将它们全部“淹没”（标记为非岛屿，比如标记为‘2’）。这些岛屿因为接触边界，所以不是封闭的。处理完边界后，剩下的陆地就是封闭岛屿，再用标准方法计数即可。

def closedIsland(grid): if not grid: return 0 m, n = len(grid), len(grid[0]) dirs = [(-1,0),(1,0),(0,-1),(0,1)] def dfs(i, j): if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != 0: # 注意，这里是找‘0’（水）还是‘1’（陆）？题目通常定义陆地为1，水为0。封闭岛屿是陆地被水包围。 return grid[i][j] = 2 # 标记为已访问/非封闭区域 for d in dirs: dfs(i+d[0], j+d[1]) # 1. 淹没所有与边界相连的陆地（这些不是封闭岛） # 注意：这里容易混淆。封闭岛屿是“陆地”被“水”包围。 # 所以，我们先要把四周边界上的“陆地”淹没掉。 for i in range(m): for j in range(n): if (i == 0 or i == m-1 or j == 0 or j == n-1) and grid[i][j] == 0: # 假设0是陆地，1是水？不，通常1是陆地。 # 等等，需要根据题目定义调整。假设 grid[i][j] == 1 是陆地。 # 我们淹没边界上的陆地。 pass # 为了清晰，我们重写：假设1是陆地，0是水。 # 封闭岛屿：被水（0）包围的陆地（1）。 # 步骤：先淹没所有与边界相连的陆地（因为它们不封闭）。 for i in range(m): if grid[i][0] == 1: dfs(i, 0) # 左边界 if grid[i][n-1] == 1: dfs(i, n-1) # 右边界 for j in range(n): if grid[0][j] == 1: dfs(0, j) # 上边界 if grid[m-1][j] == 1: dfs(m-1, j) # 下边界 # 2. 现在，剩下的陆地都是封闭岛屿，统计其数量 count = 0 for i in range(m): for j in range(n): if grid[i][j] == 1: count += 1 dfs(i, j) # 淹没整个封闭岛，避免重复计数 return count

这个变体很好地考察了对问题定义的细微理解和对预处理（Pre-processing）技巧的掌握。

7. 性能对比与选型指南

在实战中，我们该如何选择呢？光看理论不够，我用自己的环境（Python 3.8, 6核CPU）对一个 500x500，陆地密度约30%的随机网格进行了简单测试（次数不多，仅作趋势参考）：

选型决策流：

1. 问题是否静态？如果只是单次计算岛屿数量，直接跳到第2步。如果网格会动态变化（例如，后续会不断将某些‘0’变成‘1’），或者需要频繁查询两个点是否在同一岛屿上，无脑选择并查集(UF)。这是UF的绝对优势领域。
2. 网格规模多大？如果网格边长超过500，或者你无法预知输入大小，避免递归DFS，优先选择迭代DFS或BFS。
3. 需要层序信息吗？如果需要计算岛屿的“最小到边界的距离”这类问题，BFS的层序特性天然适合。
4. 追求极简代码？如果是在白板面试或快速原型中，递归DFS的简洁性是无可替代的。只需口头说明递归深度风险及迭代优化方案即可。

我个人在大多数一次性静态统计场景下，会优先使用迭代DFS。它在代码简洁性、内存可控性和避免递归风险之间取得了很好的平衡。而并查集，我会把它当作一个专门的工具，留在需要处理动态连通性的“武器库”里。

最后，再分享一个我调试这类问题的小技巧：可视化。对于复杂的网格或奇怪的bug，不要只盯着代码看。将网格打印出来，或者用简单的图形字符在控制台画出每一步的状态，往往能一眼看出问题所在。算法不只是抽象的数学，更是解决实际问题的工程。