Python中用dict表示有向图邻接表时，应统一用空列表作为每个键的值（如{'A':['B','C'],'B':['D'],'C':[],'D':[]}），避免混用list/set/None或缺失键；动态构建推荐defaultdict(list)，禁用set以防BFS/DFS遍历顺序不可复现。
用 dict 表示图时，邻接表结构怎么写才不踩坑
Python 里最轻量的有向图表示就是 dict：键是节点，值是该节点能直接到达的节点列表（或集合）。但容易错在「值类型不统一」——比如混用 list、set、None 或缺失键，导致遍历时抛 KeyError 或跳过边。
- 统一用
dict的每个键对应一个list（哪怕为空），避免键缺失：graph = {<br> 'A': ['B', 'C'],<br> 'B': ['D'],<br> 'C': [],<br> 'D': []<br>} - 如果图动态构建，初始化时用
defaultdict(list)，比手动检查键更安全 - 别用
set当值——虽然查重快，但 BFS/DFS 需要稳定遍历顺序，而set无序，可能让路径结果不可复现
BFS 搜索最短路径时，为什么必须记录已访问节点和前驱节点
单向有向图允许环，不记录访问状态会死循环；只记录访问状态又无法还原路径。所以 BFS 队列存节点，同时用两个辅助结构：visited（set）防重复入队，parent（dict）记路径来源。
-
visited必须在入队时标记，不是出队时——否则同一节点可能被多次加入队列 -
parent只需存「谁走到当前节点」，不需要存距离，路径长度由层级自然体现 - 终点找不到时，别忘了返回
None或空列表，而不是静默失败
示例片段（从 start 到 end）：
from collections import deque<br><br>def bfs_path(graph, start, end):<br> if start == end:<br> return [start]<br> queue = deque([start])<br> visited = {start}<br> parent = {}<br><br> while queue:<br> node = queue.popleft()<br> for neighbor in graph.get(node, []):<br> if neighbor == end:<br> # 回溯构造路径<br> path = [end]<br> while node in parent:<br> path.append(node)<br> node = parent[node]<br> path.append(start)<br> return path[::-1]<br> if neighbor not in visited:<br> visited.add(neighbor)<br> parent[neighbor] = node<br> queue.append(neighbor)<br> return None
DFS 递归实现路径搜索，如何避免栈溢出和重复遍历
递归 DFS 在深图中容易触发 RecursionError，且没做访问控制会陷入环。关键不是「用不用递归」，而是「怎么剪枝」。
立即学习“Python免费学习笔记（深入）”；
- 必须传入当前路径（
path）和已访问集合（seen），两者都要在递归调用前更新、回溯后还原 - 用
seen而非仅靠path判断环——因为路径含起点到当前节点，但图可能有跨层环（如 A→B→C→A） - 若只要一条路径，找到就
return；若要所有路径，收集后继续，但注意内存增长 - 深度超 1000 时，建议改用显式栈的迭代 DFS，避免依赖系统递归限制
networkx 能不能直接替代手写？什么情况下不该用
如果只是跑一次简单路径搜索，networkx 是过度设计：它加载慢、依赖重、对象封装深，且默认图结构比纯 dict 多好几层间接。
- 适合场景：需要拓扑排序、强连通分量、中心性计算等复杂图算法时再引入
- 硬伤：
nx.shortest_path(graph, start, end)底层仍是 BFS，但输入必须转成nx.DiGraph，开销远大于原生dict+ 几十行代码 - 调试困难：错误信息常指向内部方法，不如自己写的逻辑一眼看清哪步出错
真正省事的折中方案是封装一个轻量类，把图存储、BFS/DFS 方法打包，不引入外部依赖，也避免每次重写。
路径搜索真正的复杂点不在数据结构选择，而在「图是否带权」「是否允许多重边」「是否需要支持动态增删」——这些一加，dict 就得立刻换成更明确的邻接矩阵或边列表，而不是硬撑。
