BFS（广度优先搜索） 是一种用于遍历或搜索树、图等结构的算法，其核心思想是 逐层探索，优先访问距离起点最近的节点。以下是详细解析：
一、算法核心思想
- 层级遍历：从起点出发，先访问所有直接相邻的节点（第一层），再访问这些相邻节点的相邻节点（第二层），依此类推。
- 最短路径特性：在无权图中，BFS 首次访问到目标节点时的路径一定是最短路径。
二、算法实现步骤
- 初始化队列：将起点放入队列，并标记为已访问。
- 循环处理队列：
- 从队列头部取出一个节点。
- 遍历该节点的所有未访问的相邻节点。
- 将这些相邻节点标记为已访问，并加入队列尾部。
- 终止条件：队列为空时结束。
from collections import dequedef bfs(graph, start):visited = set()queue = deque([start])visited.add(start)while queue:node = queue.popleft()print(node, end=' ') # 处理当前节点for neighbor in graph[node]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)
三、关键数据结构：队列
- 先进先出（FIFO） 的特性保证了层级遍历的顺序。
- 队列中保存的是 待处理的节点，确保按层级顺序扩展。
四、典型应用场景
- 无权图的最短路径（如迷宫问题、社交网络关系）。
- 层级遍历树或图（如二叉树的层序遍历）。
- 状态空间搜索（如华容道、八数码问题）。
- 网络爬虫：按距离逐层抓取网页。
五、时间复杂度分析
- 时间复杂度：
O(V + E)，其中V是节点数，E是边数。 - 空间复杂度：
O(V)，最坏情况下队列需要存储所有节点。
六、BFS vs DFS
| 特性 | BFS | DFS |
|---|---|---|
| 遍历顺序 | 按层级逐层访问 | 深度优先，一条路走到黑 |
| 数据结构 | 队列 | 栈（递归隐式使用栈） |
| 最短路径 | 天然支持（无权图） | 需要额外记录路径长度 |
| 空间复杂度 | 较高（保存一层的所有节点） | 较低（路径上的节点） |
七、实战示例：迷宫最短路径
问题：在 0（可走）和 1（障碍）组成的矩阵中，找到从起点 (0,0) 到终点 (m-1,n-1) 的最短步数。
from collections import dequedef shortest_path(maze):m, n = len(maze), len(maze[0])directions = [(-1,0), (1,0), (0,-1), (0,1)]queue = deque([(0, 0, 0)]) # (x, y, steps)visited = set((0, 0))while queue:x, y, steps = queue.popleft()if x == m-1 and y == n-1:return stepsfor dx, dy in directions:nx, ny = x+dx, y+dyif 0<=nx<m and 0<=ny<n and maze[nx][ny]==0 and (nx,ny) not in visited:visited.add((nx, ny))queue.append((nx, ny, steps+1))return -1 # 无通路
八、常见陷阱
- 忘记标记已访问节点：导致重复访问和死循环。
- 错误处理队列顺序：使用栈（后进先出）会退化为DFS。
- 忽略边界条件：如矩阵越界、障碍判断。
掌握BFS的关键在于理解其 层级扩散 的本质，结合队列实现，能够高效解决最短路径和状态搜索问题。