广度优先搜索（BFS）在解决最短路径问题、图遍历和状态搜索等问题时非常高效，但其性能可以通过多种优化技巧进一步提升

广度优先搜索（BFS）在解决最短路径问题、图遍历和状态搜索等问题时非常高效，但其性能可以通过多种优化技巧进一步提升。

以下是对 BFS 优化技巧的深度解析，涵盖空间优化、时间优化、算法改进及实用建议，力求系统且清晰。

一、空间优化技巧

1.1 复用输入数据

• 适用场景：在网格类问题（如迷宫、岛屿问题）中，输入数组（如网格）通常可以复用为访问标记或距离记录。
• 方法：
  • 直接在输入数组上标记已访问的节点（例如将网格值从 0 改为 -1 表示已访问）。
  • 若需要记录距离，可将网格值改为距离值（前提是原始值不会被后续逻辑需要）。
• 示例：
  • 在 LeetCode 1091（二进制矩阵中的最短路径）中，可以直接在网格上标记已访问的单元格，避免额外的 visited 数组。
• 效果：空间复杂度从 O(mn) 降为 O(1)（m x n 为网格大小），仅需队列空间 O(mn)。
• 注意：确保修改输入不会影响其他逻辑，或在题目允许的情况下使用。

代码示例（迷宫问题，复用网格）：python

from collections import deque def shortest_path_maze(grid, start, end): if not grid or grid[start[0]][start[1]] == 1 or grid[end[0]][end[1]] == 1: return -1 m, n = len(grid), len(grid[0]) queue = deque([(start[0], start[1], 0)]) # (x, y, distance) grid[start[0]][start[1]] = -1 # 标记已访问 directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] while queue: x, y, dist = queue.popleft() if (x, y) == end: return dist for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0: grid[nx][ny] = -1 # 标记已访问 queue.append((nx, ny, dist + 1)) return -1

1.2 使用位图或哈希集

• 适用场景：在状态搜索或图遍历中，节点数量较大时，visited 数组可能占用大量空间