图的字典表示：Python邻接表存储与图算法实战

翻到任何一本数据结构教材的目录，5-2 图的字典表示这一节往往并不起眼，前面是邻接矩阵，后面是图的遍历，它看起来只是"顺带一提"的存储方案。但我做算法题、写爬虫解析关联关系、处理社交网络数据这么多年，越来越确认一个事实：字典表示图，才是真正从纸面走向工程的默认姿势。如果你刚学到图这一章，或者刷LeetCode时总在graph = defaultdict(list)这一步停下来想"这到底是什么结构"，这篇笔记就是给你准备的。我会用实际能跑的Python代码，把图的字典表示的三种形态、遍历套路、最短路径与最小生成树的写法，以及那些教材不会写在角落里的坑，一次性讲透。

1. 为什么计算机里存图要"另起炉灶"：邻接矩阵的天花板效应

先搞清楚图到底要存什么。一张图由顶点集合 V 和边集合 E 组成，所谓"存图"，本质上就是回答两个问题：u 和 v 之间有没有边，以及如果有，边的权值是多少。教材先教邻接矩阵，因为它最直观——一个二维数组，matrix[u][v]直接给出答案，查边的时间是 O(1)，这几乎是最理想的查询性能。我用 Python 写邻接矩阵通常是这样的：

n = 5 graph = [[0] * n for _ in range(n)] graph[0][1] = 1 # 顶点0到顶点1有一条边 graph[1][0] = 1 # 无向图需要对称地再写一次

这段代码本身没有问题，问题出在它背后那张"账单"上。

1.1 邻接矩阵的 O(V^2) 空间账单怎么算

空间复杂度是 O(V^2)，V 是顶点数。4 个顶点是 16 个格子，很多人觉得"也没多大啊"，于是继续往上加。加到 1000 个顶点，矩阵变成 100 万个格子；加到 10000 个顶点，就是 1 亿个格子。Python 里一个普通的int对象占 28 字节左右，1 亿个格子就是 2.8 GB，这还只是一个矩阵对象本身。我当年第一次尝试用邻接矩阵存 5000 个节点的路网数据时，程序直接内存报错，换了一台机器才跑起来。

比内存更致命的是稀疏性。真实世界的大多数图都非常"空"：社交网络里一个人认识几百个朋友，但整个平台有几亿用户；地图路网里每个路口只连着三四条路；网页之间的链接更是稀疏到可以忽略不计。对这些图来说，邻接矩阵里绝大多数格子都是 0，它们白白占着内存，却什么信息都没提供。如果坚持用邻接矩阵，你不是在存图，你是在给图"烧钱"。

还有一层隐藏成本容易被忽略：动态增删顶点。矩阵的大小在创建时就固定了，想加一个顶点，你得重新分配一个更大的二维数组，再把旧数据搬过去；删掉一个顶点，更要命，所有和它有关的行列都要挪位置，单次操作是 O(V^2) 的代价。而"动态"恰恰是工程里最常见的需求——爬虫不断发现新页面，社交网络不断涌入新用户，没有人能提前知道最终顶点个数。

1.2 字典的哈希映射恰好补上这块短板

Python 的字典（dict）底层是哈希表，它天然解决了一个问题：拿到一个键，平均 O(1) 时间查出对应的值。这正好可以拿来改造成"查邻居"操作——把顶点当成键，把这个顶点的所有邻居当成值。查询"u 有哪些邻居"变成一次字典查询，查询"u 和 v 是否相邻"变成一次集合/列表成员判断。空间上，只存真实存在的边，复杂度是 O(V + E)，稀疏图下和邻接矩阵的 O(V^2) 相比，节省两个数量级都很正常。

更重要的是字典的"动态"属性。新顶点出现，直接graph[new_node] = []就完了，不涉及任何搬移；删顶点，del graph[node]再顺手从所有邻居列表里清理一遍，代价只和这个顶点的度数有关，而不是和整张图的规模有关。这种"按需成长"的能力，是固定大小的矩阵永远给不了的。

还有个语言层面的巧合：字典的键不限于整数，字符串、元组都可以。这对实际项目太友好了——图的顶点往往不是"编号 0 到 n-1"，而是 IP 地址、用户名、URL、城市名。用邻接矩阵你得先做一遍"名字到编号"的映射，用字典表示图，名字本身就能当键，省掉一整层映射逻辑。

记住这个结论：稠密图、顶点数量小、需要频繁判断任意两点是否相邻，选邻接矩阵；稀疏图、顶点数量大、结构动态变化，选邻接表/字典。真实项目里 99% 的情况属于后者。

2. 三种字典图结构：从邻接集合到嵌套字典

字典表示图不是只有一种写法，根据图有没有方向、有没有权值，需要选不同的"值"类型。我把它们分成三种形态，从最简单到最通用，逐一说清楚。

2.1 最轻量的形态：顶点映射到邻居集合

如果图是无向图，而且不关心权重，最简单的方式是用"顶点 -> 邻居集合"：

graph = { "A": {"B", "C"}, "B": {"A", "C", "D"}, "C": {"A", "B", "D"}, "D": {"B", "C"} }

值用set而不是list，有两个好处：一是天然去重，反复添加同一条边不会产生重复项；二是集合的in判断是哈希查找，平均 O(1)，比列表的线性扫描快。这个形态特别适合做"两人是否认识""两个节点是否连通"这类判断密集的场景。

要注意一个无向图的特性：对称性。A的邻居里有B，B的邻居里就必须有A。这是最容易出错的地方——我见过不少人在测试阶段手写小图时忘了对称更新，导致遍历结果莫名其妙缺少节点。如果你经常手工构造测试数据，建议写一个辅助函数来规避：

def add_undirected_edge(graph, u, v): graph.setdefault(u, set()).add(v) graph.setdefault(v, set()).add(u)

setdefault是关键，新顶点第一次出现时自动创建空的set，省掉先判断键是否存在的一整轮逻辑。

2.2 有向图的标准姿势：顶点映射到邻居列表

有向图里边的方向有意义，A -> B不代表B -> A。这时的值类型换成列表，因为我们需要保留边的顺序，而且很多算法（比如拓扑排序）依赖对邻居的稳定遍历：

graph = { "A": ["B", "C"], "B": ["D"], "C": ["D"], "D": [] }

数据结构上有个专业称呼叫"邻接表"（adjacency list），字典表示图就是邻接表的一种直接实现。为什么用列表而不是集合？主要有两个原因：第一，列表允许重复元素，某些特殊场景（比如多图、平行边）需要保留多条同向边；第二，列表遍历时保持插入顺序，在 Python 3.7+ 字典本身也有序的情况下，整个图的遍历顺序是确定的、可复现的，这对调试和测试都友好得多。

还需要注意：字典里最好把每个顶点都显式挂一个空列表。像上面"D": []，而不是干脆不写D这个键。因为后面写遍历算法时，我们经常要graph[node]直接取值，如果某个顶点没有键，就要多写一个graph.get(node, [])兜底。显式写出所有顶点，代码更简单，也方便用len(graph)直接拿到顶点总数。

2.3 嵌套字典：带权图的完全体

当边上带权重时，就不能用一个简单的邻居列表糊弄了。最自然的扩展是把"邻居"再映射一层"权重"：

graph = { "A": {"B": 5, "C": 3}, "B": {"C": 2, "D": 4}, "C": {"D": 6}, "D": {} }

读法很直白：A -> B的权重是 5，A -> C的权重是 3。查询两个顶点之间边的权重，一行代码：graph["A"].get("B")，如果返回None说明没有直接边。这种结构是 Dijkstra、Prim、Floyd 等带权算法的默认载体，后面我会给完整实现。

嵌套字典还有几个灵活的变体，按需选用：

• 自环："A": {"A": 1}表示 A 到自身有一条权为 1 的边，哈希表完全支持，邻接矩阵反而要额外处理对角线。
• 平行边（两点间多条边）：一个邻居键对应一个列表不行，因为内层值是数字而不是容器。可以改成"A": {"B": [5, 7]}，存一个权重列表，代价是取权重的逻辑变复杂。
• 节点编号是整数：直接{0: {1: 2}, 1: {0: 2}}，和字符串键完全等价，注意别把键写成int却又拿字符串'0'去查，查不到还纠结半天。

三种形态的选型可以总结成一张表，平时写代码前先对号入座：

3. 图论算法在字典表示上怎么写才优雅：BFS、DFS 与拓扑排序

图存好了，接下来就是图论算法的主场。很多初学者学算法时用的是邻接矩阵版的伪代码，一到自己写就发现"好像不太对"，因为他们手上的数据结构变了。下面我把最常见的几个算法，直接写成"字典图视角"的版本，代码都能直接跑。

3.1 BFS：队列加 visited 集合，缺一不可

BFS 的核心是"逐层扩散"，实现上需要一个队列和一个已经访问过的集合。队列用collections.deque，不要用list的 pop(0)，后者是 O(n) 的头部删除，图一大就原形毕露：

from collections import deque def bfs(graph, start): visited = {start} queue = deque([start]) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph.get(node, []): if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return order

三个容易踩的细节：

第一，visited 为什么用集合而不是列表。判断"是否已访问"是 BFS 里最高频的操作，集合是哈希查找 O(1)，列表是线性查找 O(n)。顶点数上万之后，两者差距是数量级的。

第二，入队前就要标记 visited，而不是出队时再标记。如果在popleft()之后才标记，同一个节点可能被多个邻居重复加入队列，造成重复处理，甚至在有环图上死循环。这是新手最常见的 BFS 写错姿势。

第三，graph.get(node, [])这个兜底看起来多余，但当你从一个并不存在的顶点出发时，它能让程序安静地返回空列表而不是抛 KeyError。写算法时多写这一句，能省掉大量边界调试。

3.2 DFS：递归优雅，迭代要会处理"重复入栈"

深度优先用递归最直观：

def dfs_recursive(graph, node, visited=None): if visited is None: visited = set() visited.add(node) print(node, end=" ") for neighbor in graph.get(node, []): if neighbor not in visited: dfs_recursive(graph, neighbor, visited) return visited

注意visited=None的写法，不要用visited=set()当默认参数——Python 的默认参数在函数定义时就创建一次，多次调用会共享同一个集合，导致数据串台。这个坑我在项目里见过不止一次，教训深刻。

递归写法的隐患是 Python 的递归深度限制，默认只有 1000 层。如果图是一条长长的链，顶点数超过 1000，直接RecursionError。工程上更稳妥的是迭代版：

def dfs_iterative(graph, start): visited = set() stack = [start] while stack: node = stack.pop() if node in visited: continue visited.add(node) for neighbor in graph.get(node, []): if neighbor not in visited: stack.append(neighbor) return visited

迭代版里有个微妙的点：node in visited判断放在pop()之后。因为同一个节点可能被两个不同邻居先后压入栈，第一次出栈时处理完标记了 visited，第二次出栈时发现标记过就跳过。这个"允许重复压栈，出栈时去重"的策略，避免了在压栈前做复杂判断，逻辑反而更简洁。

3.3 不只是遍历：用字典回溯路径

遍历只是热身，实际应用里我们更常要的是"从起点到目标点的路径"。利用字典可以轻松记录每个节点的前驱，从而回溯出完整路径。以 BFS 为例：

from collections import deque def bfs_path(graph, start, target): parent = {start: None} queue = deque([start]) while queue: node = queue.popleft() if node == target: path = [] while node is not None: path.append(node) node = parent[node] return path[::-1] for neighbor in graph.get(node, []): if neighbor not in parent: parent[neighbor] = node queue.append(neighbor) return []

parent就是一个普通的字典，键是顶点，值是它的"上一个顶点"。BFS 天然保证第一次到达某个顶点时的路径就是最短路径（无权图上），所以回溯出来的路径就是最短路径。这个"用字典当指针数组"的思想，在带权图上也会继续用到，区别只是记录的方式不同。

3.4 拓扑排序：Kahn 算法和字典的天然配合

有向无环图（DAG）的拓扑排序，最经典的是 Kahn 算法，核心是"统计每个顶点的入度，从入度为 0 的顶点开始，一层层剥掉"。字典表示图时，统计入度几乎是一行循环的事：

from collections import deque def topological_sort(graph): indegree = {v: 0 for v in graph} for u in graph: for v in graph.get(u, []): indegree[v] = indegree.get(v, 0) + 1 queue = deque([v for v in graph if indegree[v] == 0]) result = [] while queue: u = queue.popleft() result.append(u) for v in graph.get(u, []): indegree[v] -= 1 if indegree[v] == 0: queue.append(v) return result if len(result) == len(graph) else []

两处容易被忽视的逻辑：

• indegree = {v: 0 for v in graph}先给所有顶点初始化为 0，遍历边时再累加。如果直接indegree.get(v, 0) + 1而不初始化，最后某些入度为 0 的孤立顶点根本不会出现在 indegree 字典里，后面取入度为 0 的候选顶点时就会漏掉它们。
• 返回值需要校验len(result) == len(graph)。如果图里有环，环上的顶点入度永远无法降到 0，result 就会比 graph 短。返回空列表是"检测到环"的经典信号。判断有向图是否有环，一个拓扑排序就搞定，这也是字典图上最实用的操作之一。

4. 工程化视角：字典图的进阶扩展与常见坑

知道 BFS、DFS 之后，图的基本操作就够用了。但真正的工程问题往往是：边上带权重怎么办？找最短路径怎么办？图很大怎么办？这些进阶场景里，字典表示依然游刃有余，但坑也更多。

4.1 Dijkstra：嵌套字典 + 优先队列的标准打法

带权图求最短路径，Dijkstra 是最常用的算法。它每一轮从"当前已知距离最小的未确定顶点"出发，松弛它的所有邻居。这个"取最小值"的操作如果每次遍历全图，复杂度是 O(V^2)，浪费严重；工程上要用优先队列（最小堆），Python 直接heapq：

import heapq def dijkstra(graph, start): dist = {node: float('inf') for node in graph} dist[start] = 0 heap = [(0, start)] while heap: d, u = heapq.heappop(heap) if d > dist[u]: continue for v, w in graph.get(u, {}).items(): nd = d + w if nd < dist[v]: dist[v] = nd heapq.heappush(heap, (nd, v)) return dist

几个关键点：

• graph.get(u, {}).items()，这里内层值是字典，所以直接.items()拿到 (邻居, 权重) 对。这是嵌套字典勾连 Dijkstra 的"接口"。
• if d > dist[u]: continue是必备的剪枝。同一个顶点可能被多次压入堆，只有最新（距离最短）的那次才有效，旧记录直接跳过，没有这行代码会大幅拖慢速度。
• float('inf')表示未到达，初始化时统一的无穷大，最后dist里仍为无穷大的顶点就是不可达的。这在判断连通性时非常省事。

讲个我个人踩过的坑：一开始我用heap = []每次手动 sort 来取最小，节点少的时候没感觉，换到 2000 个节点的图，慢了整整一个数量级。后来老老实实用heapq，代码量没多多少，性能直接起飞。在图上，数据结构的选型永远比循环优化的收益来得快。

4.2 Prim：最小生成树在嵌套字典图上的简洁实现

最小生成树（MST）的 Prim 算法，和 Dijkstra 长得很像，它维护的是一个"已选顶点集合"，每次从边界边里挑一条权重最小的边加入。字典版本的实现：

import heapq def prim_mst(graph, start=0): mst = [] visited = {start} edge_heap = [] for v, w in graph.get(start, {}).items(): heapq.heappush(edge_heap, (w, start, v)) total_weight = 0 while edge_heap: w, u, v = heapq.heappop(edge_heap) if v in visited: continue visited.add(v) mst.append((u, v, w)) total_weight += w for nxt, w2 in graph.get(v, {}).items(): if nxt not in visited: heapq.heappush(edge_heap, (w2, v, nxt)) return mst, total_weight

注意这里堆里存的是三元组(weight, from, to)，这样弹出时不但拿到权重，还知道这条边连的是哪两个顶点。初始化和 Dijkstra 同样的问题：内层遍历要取graph.get(start, {}).items()。如果图连通且顶点数大于 visited 的数量，说明原始图本身不连通，MST 不存在，这时候把返回结果的长度和len(graph)-1对比一下就能判断。

4.3 字典图最常见的五个坑

与其等你在调试器里耗两小时，我直接把这些年常见的坑列出来：

1. 键不存在就报 KeyError。无论你是查邻居还是查权重，用graph.get(node, [])、graph.get(u, {}).items()这类写法，代码会健壮很多。setdefault也是你的好朋友。

2. 可变默认参数。写def add_edge(g, u, v, container=[])这种签名，第二个调用者会惊喜地发现别人家的边出现在自己的容器里。默认参数只在函数定义时求值一次，改用container=None然后在函数体内判断。

3. 不可哈希的键。字典的键必须可哈希，列表、字典本身都不能当键。如果图的顶点是坐标点，用tuple而不是list：(x, y)完全可以当键，[x, y]不行。这是我被问过最多的问题之一。

4. 键的插入顺序依赖。Python 3.7 起字典保持插入顺序，这本身是好事，但如果你在遍历的同时修改字典（比如 BFS 过程中往图里加顶点），会触发RuntimeError: dictionary changed size during iteration。解决办法是先取键的列表快照：for node in list(graph.keys()):，或者干脆在遍历前把要加的顶点统一收集起来。

5. 性能幻觉。字典访问是 O(1) 平均，但常数其实不小。几十万节点的超大规模图，还要追求极致性能的话，用array模块或直接上第三方库如networkx，它内部就是邻接表结构，但用 C 级别的优化做了大量加速。自己用纯 Python 字典硬扛亿级边数据，属于跟语言特性较劲。

4.4 从教材到实践：字典表示图真正解决的是什么问题

我经常跟新手说，5-2 图的字典表示这一节，表面上是在教"图怎么存"，实际上教的是一个更普适的思维模型：把关系映射成字典。对象和对象之间有联系，就把对象当键、关系当值；一个对象和多个对象有不同类型的联系，就用嵌套字典分层映射。这个模式并不局限于图论教材里的"顶点和边"，你在设计 REST API 的路由表、做数据库的外键索引、写配置文件解析器时，用的都是同一套思路。

我自己最深的体会是：字典图让"图的构建"变成一件随手可以做的事。以前用邻接矩阵，我会不自觉地想"先确定顶点数量、再绘图、再写算法"，流程很重；用字典图之后，随手graph.setdefault(node, []).append(neighbor)就建了一条边，图的构建和算法彻底解耦了。这种感觉很像从"先规划再行动"变成了"边行动边规划"，对快速原型验证特别重要。

最后分享一个实用小技巧：调试字典图时，别急着print(graph)——大图的输出能把你淹没。写一个简短的函数，只打印每个顶点的度和邻居数量：

def summarize_graph(graph, limit=10): for i, node in enumerate(graph): if i >= limit: print("...") break if isinstance(graph[node], dict): print(f"{node} -> {len(graph[node])} weighted edges") else: print(f"{node} -> {len(graph[node])} neighbors")

先看整体规模是否符合预期，再决定要不要深入某几个顶点的细节，效率高得多。图这种结构藏得很深，用眼睛看原始字典是看不出来的，借助度和规模的统计，边界条件往往一眼就能发现端倪。