邻接表、逆邻接表与度

写拓扑排序时需要每个顶点的入度，写 BFS 又需要快速拿到所有出边。同一张有向图，两种需求对应的存储方式不同。整理一下邻接表、逆邻接表和入度出度的关系。

邻接表

邻接表对每个顶点记录它能直接到达的顶点（后继/出边）。只存实际存在的边，空间是 O(V+E)，图越稀疏越省。

# 有向图：A → B，A → C，B → C
graph = {
    "A": ["B", "C"],
    "B": ["C"],
    "C": [],
}
 
# 遍历 A 的所有出边
for nxt in graph["A"]:
    print(nxt)  # B C

无向图的每条边会在两个端点的列表里各出现一次，所以空间翻倍。邻接表的代价是查一条边是否存在要遍历列表，O(degree)。

逆邻接表

逆邻接表把边反着存：每个顶点记录「能到达它的顶点」（前驱/入边）。

reverse = {v: [] for v in graph}
for u, neighbors in graph.items():
    for v in neighbors:
        reverse[v].append(u)
 
# reverse: {"A": [], "B": ["A"], "C": ["A", "B"]}

它和邻接表是同一份边信息的两种视角：邻接表顺着箭头走，逆邻接表逆着箭头走。

入度与出度

• 出度：从该顶点出发的边数，邻接表里直接数列表长度
• 入度：指向该顶点的边数，逆邻接表里直接数列表长度
• 无向图不分方向，统一叫度；每条边在两个端点各计一次

out_degree = {v: len(neighbors) for v, neighbors in graph.items()}
in_degree = {v: len(prev) for v, prev in reverse.items()}

概念	从邻接表得到	从逆邻接表得到
出度	直接数列表长度	扫描全表
入度	扫描全表	直接数列表长度

一张表里只能直接得到一个方向的度，另一个方向要么扫全表，要么另外维护一份计数。

算法里怎么用

BFS、DFS 顺着出边走，用邻接表；拓扑排序、找前驱、反向依赖，用入度和逆邻接表。Kahn 拓扑排序的典型写法：

from collections import deque
 
indegree = {v: 0 for v in graph}
for u, neighbors in graph.items():
    for v in neighbors:
        indegree[v] += 1
 
queue = deque([v for v, d in indegree.items() if d == 0])
order = []
 
while queue:
    u = queue.popleft()
    order.append(u)
    for v in graph[u]:
        indegree[v] -= 1
        if indegree[v] == 0:
            queue.append(v)

这里入度统计扫了一遍全图，之后每次删边只改相邻顶点的计数，总复杂度 O(V+E)。

维度	邻接表	逆邻接表
存储方向	出边	入边
直接得到的度	出度	入度
典型场景	BFS/DFS、正向遍历	拓扑排序、反向依赖

核心区别一句话：邻接表顺着箭头存，逆邻接表逆着箭头存，入度出度分别由逆邻接表和邻接表直接数出来。