bfs能解无权图最短路径，因其按层遍历，首次访问目标节点时边数最少；仅适用于边权相等的图，需visited防环、parent还原路径，用deque实现高效o(1)出队。
为什么 BFS 能解无权图最短路径？
因为 BFS 按层遍历，第一次访问到目标节点时，走过的边数就是最少的。这点只在所有边权重相等（即无权图或单位权图）时成立；如果边有权重，得换 Dijkstra 或 A*。
- 无向图、有向图都适用，只要边没权重
- 如果图带环，必须用
visited集合避免重复入队 - 路径还原需要额外记录每个节点的前驱（
parent字典），不能只存距离
用 collections.deque 实现标准 BFS 框架
Python 里别手写队列，直接用 deque——它 popleft() 是 O(1)，比 list.pop(0) 快得多。
from collections import deque
<p>def bfs_shortest_path(graph, start, end):
if start == end:
return [start]</p><pre class="brush:python;toolbar:false;">queue = deque([start])
visited = {start}
parent = {}
while queue:
node = queue.popleft()
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
parent[neighbor] = node
if neighbor == end:
# 逆推路径
path = []
curr = end
while curr != start:
path.append(curr)
curr = parent[curr]
path.append(start)
return path[::-1]
queue.append(neighbor)
return None # 不可达
-
graph通常是{node: [neighbor1, neighbor2]}形式 - 别漏掉
if start == end的边界判断，否则空路径会返回None -
parent只在首次发现邻居时赋值，确保是最短路上的前驱
遇到 “超时” 或 “内存爆掉” 怎么办？
BFS 本身不递归，但若图太大（比如百万级节点）、又没及时剪枝，queue 和 visited 会吃光内存。
- 先确认图是否真需要全遍历：如果只关心起点到终点的最短距离（不要路径），可提前在
if neighbor == end后直接return len(path)，不必存parent - 若图是隐式生成的（如迷宫坐标、单词变换），务必用元组/字符串作节点键，避免用可变对象（如
list）当 key 导致哈希失败或重复 - Python 默认递归限制对 BFS 无关，但若误写成 DFS 递归版本，容易触发
RecursionError
从邻接表到网格坐标的 BFS 改写要点
很多实际问题（如二维迷宫、岛屿数量）节点是 (r, c) 坐标，不是字符串或数字。
- 四方向邻居用
[(r-1,c), (r+1,c), (r,c-1), (r,c+1)]生成，再过滤出界和障碍 -
visited仍用set，但元素是(r, c)元组，不是字符串拼接 - 初始位置入队前，先检查是否越界或为障碍，否则可能多走一步再失败
# 示例：迷宫中从 (0,0) 到 (m-1,n-1) 的最短步数
def bfs_maze(maze, start, end):
if not maze or not maze[0] or maze[start[0]][start[1]] == 1:
return -1
m, n = len(maze), len(maze[0])
queue = deque([(start[0], start[1], 0)]) # (r, c, steps)
visited = {start}
dirs = [(0,1),(1,0),(0,-1),(-1,0)]
<pre class="brush:python;toolbar:false;">while queue:
r, c, steps = queue.popleft()
if (r, c) == end:
return steps
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 真正卡住的往往不是算法逻辑，而是坐标越界检查顺序、障碍判断时机、以及 visited 插入位置——插在入队前还是刚出队后，结果可能差一轮遍历。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
