DFS与BFS算法解析：岛屿问题的双解法实战-平芜编程栈

1. 算法训练营实战：岛屿问题的DFS/BFS双解法剖析

今天想和大家分享两道经典的网格类算法题目——岛屿数量(LeetCode 200)和岛屿最大面积(LeetCode 695)。这两道题是算法面试中的常客，也是理解深度优先搜索(DFS)和广度优先搜索(BFS)应用的绝佳案例。我在刷题过程中发现，很多同学容易在这类问题上陷入细节陷阱，今天就用最直白的方式拆解解题思路。

网格类问题通常会给一个由'1'(陆地)和'0'(水域)组成的二维网格，要求计算岛屿数量或找出最大岛屿面积。所谓岛屿就是被水包围的陆地，通过水平或垂直方向连接的陆地视为同一个岛屿。这类问题的核心在于如何高效地遍历和标记网格，避免重复计算。

2. 岛屿数量问题解析

2.1 基础解法框架

计算岛屿数量的标准解法是遍历整个网格，当遇到'1'时启动搜索，将相连的所有'1'标记为已访问。关键在于标记策略的选择——可以直接修改原网格，也可以使用额外的visited数组。

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或BFS dfs(grid, i, j) return count

2.2 DFS实现细节

DFS的实现通常采用递归方式，注意处理边界条件和递归终止条件：

def dfs(grid, i, j): if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1': return grid[i][j] = '0' # 标记为已访问 dfs(grid, i+1, j) dfs(grid, i-1, j) dfs(grid, i, j+1) dfs(grid, i, j-1)

注意：在Python中处理大型网格时，递归深度可能超出限制，这时就需要使用BFS或迭代式DFS。

2.3 BFS实现方案

BFS使用队列实现，适合避免递归深度问题：

from collections import deque def bfs(grid, i, j): queue = deque() queue.append((i, j)) grid[i][j] = '0' 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<len(grid) and 0<=ny<len(grid[0]) and grid[nx][ny] == '1': grid[nx][ny] = '0' queue.append((nx, ny))

2.4 复杂度分析

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

DFS最坏情况是O(M×N)（网格全为陆地时的递归栈）
BFS通常是O(min(M,N))，因为队列中最多同时存储网格对角线长度的节点

3. 岛屿最大面积问题解析

3.1 解法调整思路

在岛屿数量代码基础上，我们需要在每次搜索时计算当前岛屿的面积。只需在DFS/BFS过程中增加一个计数器：

def maxAreaOfIsland(grid): max_area = 0 rows, cols = len(grid), len(grid[0]) for i in range(rows): for j in range(cols): if grid[i][j] == 1: max_area = max(max_area, dfs_area(grid, i, j)) return max_area

3.2 DFS面积计算实现

def dfs_area(grid, i, j): if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != 1: return 0 grid[i][j] = 0 return 1 + dfs_area(grid,i+1,j) + dfs_area(grid,i-1,j) \ + dfs_area(grid,i,j+1) + dfs_area(grid,i,j-1)

3.3 BFS面积计算实现

def bfs_area(grid, i, j): queue = deque([(i, j)]) grid[i][j] = 0 area = 1 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<len(grid) and 0<=ny<len(grid[0]) and grid[nx][ny] == 1: grid[nx][ny] = 0 area += 1 queue.append((nx, ny)) return area

4. 常见问题与优化技巧

4.1 边界条件处理

新手常犯的错误是忘记检查网格边界。在访问grid[i][j]前，务必确认i和j在合法范围内。一个实用的技巧是定义方向数组：

directions = [(-1,0),(1,0),(0,-1),(0,1)] for dx, dy in directions: nx, ny = i+dx, j+dy if 0<=nx<rows and 0<=ny<cols: # 安全访问grid[nx][ny]

4.2 避免重复计算

确保每个'1'只被处理一次。在修改原网格时，将访问过的'1'改为'0'是最简单的方法。如果要求保持原网格不变，就需要额外的visited矩阵：

visited = [[False for _ in range(cols)] for _ in range(rows)]

4.3 性能优化建议

对于特别大的网格，BFS通常比DFS更稳定，因为不会出现栈溢出
可以使用迭代式DFS替代递归DFS：

def dfs_iterative(grid, i, j): stack = [(i, j)] grid[i][j] = '0' while stack: x, y = stack.pop() for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]: nx, ny = x+dx, y+dy if 0<=nx<len(grid) and 0<=ny<len(grid[0]) and grid[nx][ny] == '1': grid[nx][ny] = '0' stack.append((nx, ny))

4.4 实际面试中的变种问题

面试官可能会在基础问题上增加变种要求，例如：

允许对角线连接也算作同一岛屿
需要输出所有岛屿的位置信息
网格是动态变化的（如随时间新增/减少陆地）
需要并行计算处理超大规模网格

准备这类问题时，建议先掌握基础解法，再思考可能的扩展方向。

5. 代码实现完整示例

以下是岛屿最大面积问题的完整Python解决方案：

from collections import deque class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: if not grid: return 0 max_area = 0 rows, cols = len(grid), len(grid[0]) for i in range(rows): for j in range(cols): if grid[i][j] == 1: max_area = max(max_area, self.bfs_area(grid, i, j)) return max_area def bfs_area(self, grid, i, j): queue = deque([(i, j)]) grid[i][j] = 0 area = 1 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<len(grid) and 0<=ny<len(grid[0]) and grid[nx][ny] == 1: grid[nx][ny] = 0 area += 1 queue.append((nx, ny)) return area

对于需要保持原网格不变的情况，可以这样修改：

def maxAreaOfIsland(grid): if not grid: return 0 max_area = 0 rows, cols = len(grid), len(grid[0]) visited = [[False for _ in range(cols)] for _ in range(rows)] for i in range(rows): for j in range(cols): if grid[i][j] == 1 and not visited[i][j]: area = 0 stack = [(i, j)] visited[i][j] = True while stack: x, y = stack.pop() area += 1 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: if grid[nx][ny] == 1 and not visited[nx][ny]: visited[nx][ny] = True stack.append((nx, ny)) max_area = max(max_area, area) return max_area

6. 单元测试与验证

编写测试用例验证算法正确性：

import unittest class TestIslandProblems(unittest.TestCase): def test_numIslands(self): grid1 = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] self.assertEqual(numIslands(grid1), 3) grid2 = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ] self.assertEqual(numIslands(grid2), 1) def test_maxAreaOfIsland(self): grid3 = [ [0,0,1,0,0], [0,1,1,1,0], [0,0,1,0,0], [0,0,0,0,0] ] self.assertEqual(maxAreaOfIsland(grid3), 5) grid4 = [ [1,1,0,0,1], [1,0,0,0,0], [0,0,1,1,0], [0,0,0,0,1] ] self.assertEqual(maxAreaOfIsland(grid4), 3) if __name__ == '__main__': unittest.main()