邻接表、逆邻接表与度

同一张有向图，可以从两个方向看：从一个顶点出发，接下来能到哪里；站在一个顶点上，之前能从哪里过来。邻接表记录前一种关系，逆邻接表记录后一种关系，出度和入度则是把这两种关系的数量数出来。

先固定一张图，后面的概念都用它说明：

A ──→ B ──→ D
│           ↑
└──→ C ────┘

它包含四条有向边：

A → B
A → C
B → D
C → D

箭头有起点和终点。比如 A → B 的起点是 A，终点是 B。从 A 看，这是一条出边；从 B 看，这是一条入边。

邻接表

邻接表（Adjacency List）给每个顶点保存一份列表，列表里是从它出发、沿一条边可以直接到达的顶点：

顶点 → 它能直接到达的顶点

上面的图写成邻接表是：

A → [B, C]
B → [D]
C → [D]
D → []

逐项来看：

• A → [B, C]：A 有两条出边，分别到 B 和 C
• B → [D]：B 有一条出边，到 D
• C → [D]：C 有一条出边，到 D
• D → []：D 也是图中的顶点，只是没有出边

D 后面的空列表不能随意省掉。如果代码通过邻接表的 key 枚举全部顶点，省掉 D 就会让它看起来像“不在图里”，而不是“在图里但没有出边”。

Python 中常用字典保存“顶点到邻居列表”的映射：

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": [],
}
 
# 从 A 出发可以直接到达 B 和 C
for nxt in graph["A"]:
    print(nxt)

输出：

B
C

这里的“相邻”带有方向。B 出现在 graph["A"] 中，只说明存在 A → B，并不说明存在 B → A。

无向图没有箭头，一条边需要在两个端点的列表中各存一次。例如无向边 A—B 会同时表现为 B 在 A 的列表中、A 在 B 的列表中：

undirected_graph = {
    "A": ["B"],
    "B": ["A"],
}

邻接表只保存实际存在的连接。设顶点数为 V、边数为 E，有向图的存储量是 O(V + E)。查找某个顶点的全部邻居很直接；如果列表没有额外索引，判断某一条边是否存在，则要在对应列表中查找。

逆邻接表

逆邻接表（Reverse Adjacency List）仍然保存同一批边，只是换到终点的角度记录：

顶点 → 哪些顶点可以直接到达它

把示例图转换成逆邻接表：

A → []
B → [A]
C → [A]
D → [B, C]

例如 D → [B, C] 表示有两条边指向 D：B → D 和 C → D。它不是说 D 指向 B、C。逆邻接表的 key 仍然是当前关注的顶点，列表中保存的是它的前驱。

邻接表和逆邻接表可以并排对照：

顶点	邻接表：从它能到谁	逆邻接表：谁能到它
A	B、C	无
B	D	A
C	D	A
D	无	B、C

从邻接表生成逆邻接表时，遍历每条 u → v，把 u 放进 reverse[v]：

reverse = {v: [] for v in graph}
for u, neighbors in graph.items():
    for v in neighbors:
        reverse[v].append(u)
 
print(reverse)

结果：

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

构建过程访问每个顶点一次、每条边一次，时间和额外空间都是 O(V + E)。

入度与出度

度（Degree）描述一个顶点连接了多少条边。有向图把方向拆开后，分成入度和出度：

• 出度（Out-degree）：以该顶点为起点的边数
• 入度（In-degree）：以该顶点为终点的边数

仍然逐个数示例图中的箭头：

顶点	指向它的边	入度	从它出发的边	出度
A	无	0	A→B、A→C	2
B	A→B	1	B→D	1
C	A→C	1	C→D	1
D	B→D、C→D	2	无	0

所以列表长度正好对应度数：

出度(v) = len(graph[v])
入度(v) = len(reverse[v])

out_degree = {v: len(neighbors) for v, neighbors in graph.items()}
in_degree = {v: len(prev) for v, prev in reverse.items()}
 
# out_degree: {"A": 2, "B": 1, "C": 1, "D": 0}
# in_degree:  {"A": 0, "B": 1, "C": 1, "D": 2}

只有邻接表时也能算入度，只是不能对单个顶点直接读取，需要扫描所有边：

in_degree = {v: 0 for v in graph}
 
for u, neighbors in graph.items():
    for v in neighbors:
        in_degree[v] += 1

遍历到 u → v 时，v 多了一条入边，所以执行 in_degree[v] += 1。整张图扫描完成后，结果和 len(reverse[v]) 相同。

已有结构	可以直接得到	另一方向怎么得到
邻接表	出度	扫描全部边统计入度
逆邻接表	入度	扫描全部边统计出度

逆邻接表和入度数组不是同一个东西。reverse["D"] 保存具体有哪些前驱，即 ["B", "C"]；in_degree["D"] 只保存前驱的数量，即 2。只关心数量时，单独维护入度数组比保存完整逆邻接表更省空间。

无向图不区分入度和出度，通常直接称为“度”。一条普通无向边会让两个端点的度各加一。有向图中的自环 A → A 则会让 A 的入度和出度各加一。

边的含义由场景决定

A → B 永远表示方向从 A 到 B，但“这条边在业务上代表什么”需要先约定。

在任务依赖图中，常见约定是：

A → B 表示 A 完成后，B 才能开始

按这个约定：

• graph[A] 是 A 完成后可能被推进的后继任务，也就是依赖 A 的任务
• reverse[B] 是 B 开始前要完成的前驱任务，也就是 B 所依赖的任务
• in_degree[B] 是 B 尚有多少个前置依赖

因此，不能脱离边的定义直接说“入度就是我依赖别人的数量”。这句话只在箭头按照“前置任务 → 后继任务”绘制时成立；如果系统把边定义为“当前任务 → 它依赖的任务”，含义会反过来。

在遍历和拓扑排序中怎么用

BFS 和 DFS 通常从一个顶点沿出边继续访问，所以直接读取邻接表。例如从 A 开始：

A 的邻居是 B、C
B 的邻居是 D
C 的邻居也是 D

遍历时要另外维护 visited，否则 D 可能从 B、C 两条路径被重复处理。

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)
 
print(order)  # A 会在 B、C 之前，D 会在 B、C 之后

以示例图为例，变化过程是：

时刻	取出的顶点	入度变化	新进入队列的顶点
初始	无	A=0，B=1，C=1，D=2	A
处理 A	A	B: 1→0，C: 1→0	B、C
处理 B	B	D: 2→1	无
处理 C	C	D: 1→0	D
处理 D	D	无	无

B 和 C 谁先出队都可以，因此合法结果可能是 A, B, C, D，也可能是 A, C, B, D。两种结果都满足每条边的起点排在终点之前。

这里不需要逆邻接表。处理完 A 后，需要找到 A 指向的 B、C 并减少它们的入度，这正是邻接表提供的信息。逆邻接表适合另一类查询：查看 B 的所有前驱、从某个结果反向追溯来源，或者确认一个任务具体依赖了谁。

入度统计先扫描一遍全图，排序时每个顶点入队一次、每条边处理一次，总时间复杂度是 O(V + E)。如果最终得到的 order 少于 V 个顶点，说明仍有顶点的入度无法降为 0，图中存在环。

三个结构各自保存什么

结构	v 对应的内容	回答的问题
graph[v]	v 的全部后继	从 v 出发能直接到谁？
reverse[v]	v 的全部前驱	谁能直接到 v？
out_degree[v]	v 的后继数量	有多少条边从 v 出发？
in_degree[v]	v 的前驱数量	有多少条边指向 v？

邻接表和逆邻接表保留“具体是谁”，度只保留“有几个”。它们不是四套互不相关的概念，而是同一批有向边在方向和信息粒度上的不同表示。