用dict做邻接表比list索引快，因其天然支持非连续键（如字符串、UUID），避免映射开销；defaultdict(list)自动初始化，简化边插入；带权图宜用defaultdict(dict)实现O(1)查权重；但需警惕访问不存在键触发自动创建的副作用。
用 dict 做邻接表，为什么比 list 索引快？
因为图的顶点名常常不是连续整数（比如是字符串 "A"、"node_123" 或 UUID），用 list 就得额外维护映射表，查顶点要 O(1) 哈希却换来 O(n) 映射开销。而 dict 天然支持任意不可变键，插入、查邻居都是平均 O(1)，没有索引越界风险，也不需要预分配大小。
关键点：邻接表本质是「顶点 → 邻居集合」的映射，dict 是最贴近语义且零成本的实现。
defaultdict(list) 是最简实用起点
手动检查键是否存在再 append 很啰嗦，defaultdict 自动初始化空 list，写边时不用判空：
from collections import defaultdict
graph = defaultdict(list)
graph["A"].append("B")
graph["A"].append("C")
graph["B"].append("C")
# 无需 if "A" not in graph: graph["A"] = []注意：defaultdict(list) 允许重复边（比如两次 graph["A"].append("B")），如果业务要求去重，就该换 defaultdict(set) ——但要注意 set 不保证顺序，且不能存不可哈希对象（如嵌套 dict/list）。
立即学习“Python免费学习笔记（深入）”；
带权重的邻接表怎么组织？别用二元组列表
存 [("B", 5), ("C", 3)] 看似直观，但查某条边权重要遍历；更高效的是用 dict 套 dict：
graph = defaultdict(dict) graph["A"]["B"] = 5 graph["A"]["C"] = 3 graph["B"]["C"] = 1 # 查 A→B 权重：graph["A"]["B"] → O(1) # 判断是否存在： "B" in graph["A"] → O(1)
缺点：内存略高（每个邻居多一层哈希表），但换来的是随机访问和存在性判断的常数时间。如果边数极大且只做遍历，二元组列表也够用；但只要涉及「查某对顶点是否有边」「改某条边权重」，嵌套 dict 更稳。
小心 defaultdict 的「自动创建」副作用
这是最容易踩的坑：只要访问一个不存在的键（哪怕只是读），defaultdict 就会调用工厂函数新建一项。比如：
if "D" in graph: # ✅ 安全，不触发创建
...
if graph["D"]: # ❌ 触发 graph["D"] = list()，污染数据！
for neighbor in graph["D"]: # 同样触发创建正确做法：
- 用
key in dict判断存在性 - 用
dict.get(key, default)获取值（不会创建新键） - 遍历时用
graph.keys()或graph.items()，别直接for k in graph然后在循环里写graph[k]
真正复杂的图操作（比如 BFS/DFS）里，多一次无意识的键创建可能让算法跑偏或内存暴涨——这比性能问题更难 debug。
