图的邻接表实现推荐用dict而非list，因list在稀疏图中浪费空间且不支持非整数顶点；dict提供O(1)查找和动态扩容能力，工程实践中更稳妥。
图的邻接表实现必须用 dict 而不是 list
用 list 存顶点索引容易在稀疏图中浪费空间，且无法直接支持非整数顶点（比如字符串节点名）。dict 提供 O(1) 的顶点查找和动态扩容能力，是实际工程中最稳妥的选择。
常见错误是把图初始化成 graph = [[] for _ in range(n)]，结果发现加边时要反复检查索引越界、无法处理 "A" → "B" 这类边。正确做法是：
graph = {}
def add_edge(u, v):
if u not in graph:
graph[u] = []
graph[u].append(v)
# 无向图还需：if v not in graph: graph[v] = []; graph[v].append(u)
bfs() 函数必须显式维护 visited 集合和 queue 列表
Python 的 collections.deque 是 BFS 队列的最优选择——list.pop(0) 是 O(n)，而 deque.popleft() 是 O(1)。漏掉 visited 会导致环路死循环，尤其在有向图中极易复现。
典型错误写法：if neighbor not in queue: —— 这既不能防重入，也无法覆盖已出队但未访问的节点。
立即学习“Python免费学习笔记（深入）”；
- 必须用独立的
set记录已访问节点，初始化为visited = {start} - 入队前判断：
if neighbor not in visited:，然后立即visited.add(neighbor) - 不要等出队再标记，否则同一节点可能被多次入队
遍历顺序依赖 graph[u] 的插入顺序，不保证字典序或数值序
Python 3.7+ 的 dict 保持插入顺序，但如果你用 graph[u].sort() 或手动排序，会改变 BFS 层内扩展顺序。这本身没有错，但要注意：标准 BFS 只要求同层节点“某一种”顺序被访问，不强制字典序。
容易踩的坑：
- 误以为
for neighbor in graph.get(u, []):会自动按字母/数字排序 → 实际就是插入顺序 - 在调试时手动改了边的添加顺序，导致测试用例通过但线上行为不一致
- 用
defaultdict(list)却忘了对每个新顶点做graph.setdefault(u, [])初始化，导致 KeyError
从起点到终点的最短路径需要额外记录 parent 字典
BFS 本身只回答“是否可达”和“距离多少”，不保存路径。要还原路径，必须在访问每个节点时记下它的前驱节点。
关键点：
-
parent = {start: None}初始化，避免起点无父节点引发 KeyError - 每次成功入队新节点
v时，设parent[v] = u - 路径重建用 while 循环逆推：
path = []；while node is not None:；path.append(node)；node = parent[node]；最后path[::-1] - 如果终点不在
parent中，说明不可达，别直接索引
没存 parent 就想回溯路径，只能重新跑一遍 BFS 或改用 DFS —— 这不是优化，是设计缺失。
