拓扑排序（Topological Sorting）是对一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点进行线性排序，使得对于图中的每一条有向边 u→v，顶点 u 在排序中都出现在顶点 v 之前。简单来说，如果存在一条从 u 指向 v 的边，那么 u 就必须排在 v 的前面。
在讨论拓扑排序之前，首先需要了解图的两种基本存储方式。邻接表（Adjacency List）使用一个数组，每个顶点对应一个列表，存储该顶点指向的所有邻居顶点。邻接矩阵（Adjacency Matrix）使用一个 V×V 的二维数组，matrix[u][v] 表示是否存在 u 到 v 的边。在拓扑排序的典型实现中，邻接表是最常用的选择，因为它能高效地遍历每个顶点的所有出边。
from collections import defaultdict, deque
# 邻接表方式构建有向图classGraph:
def__init__(self, num_vertices):
self.V = num_vertices
self.adj = defaultdict(list) # 邻接表defadd_edge(self, u, v):
"""添加有向边 u -> v"""self.adj[u].append(v)
上面的 Graph 类使用 Python 的 defaultdict 来存储邻接表。add_edge 方法添加一条从 u 指向 v 的有向边。这个类将成为后续所有拓扑排序算法实现的基石。
二、核心概念：DAG 与入度
有向无环图（DAG）
DAG 是拓扑排序的载体。有向意味着图中的边具有方向性，A→B 不同于 B→A；无环意味着不存在一条从某个顶点出发，经过若干条边后又回到该顶点的路径。DAG 的这两个性质共同保证了"线性排序"的可行性。
现实世界中 DAG 无处不在：Git 的版本历史是一个 DAG（虽然某些操作可能产生分叉，但从时间线角度看提交之间不会形成循环）；区块链的交易记录是一个 DAG；食谱的烹饪步骤是一个 DAG；甚至人体内的代谢通路也可以用 DAG 来建模。
from collections import defaultdict, deque
defkahn_topological_sort(graph):
"""Kahn算法：基于BFS的拓扑排序 Args: graph: Graph对象, 包含 V 和 adj Returns: list | None: 拓扑序列表，若有环则返回 None """# 1. 计算所有顶点的入度
indegree = [0] * graph.V
for u in range(graph.V):
for v in graph.adj[u]:
indegree[v] += 1# 2. 将入度为0的顶点加入队列
queue = deque([i for i in range(graph.V) if indegree[i] == 0])
# 3. 拓扑排序主循环
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph.adj[u]:
indegree[v] -= 1if indegree[v] == 0:
queue.append(v)
# 4. 检查是否所有顶点都被处理if len(result) != graph.V:
returnNone# 存在环，拓扑排序失败return result
defdetect_cycle_kahn(graph):
"""使用 Kahn 算法检测有向图是否存在环 Returns: bool: True 表示存在环 """
indegree = [0] * graph.V
for u in range(graph.V):
for v in graph.adj[u]:
indegree[v] += 1
queue = deque([i for i in range(graph.V) if indegree[i] == 0])
count = 0while queue:
u = queue.popleft()
count += 1for v in graph.adj[u]:
indegree[v] -= 1if indegree[v] == 0:
queue.append(v)
return count != graph.V # 处理顶点数不足，说明有环
defdetect_cycle_dfs(graph):
"""使用 DFS 三色标记法检测有向图是否存在环 Returns: bool: True 表示存在环 """
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * graph.V
has_cycle = [False]
defdfs(u):
color[u] = GRAY
for v in graph.adj[u]:
if color[v] == GRAY:
has_cycle[0] = Truereturnif color[v] == WHITE:
dfs(v)
color[u] = BLACK
for i in range(graph.V):
if color[i] == WHITE:
dfs(i)
if has_cycle[0]:
returnTruereturnFalse
环检测的重要性：在实际工程中，环的存在往往意味着系统配置错误、依赖关系矛盾或设计缺陷。例如，在包管理器中，如果软件包 A 依赖 B、B 依赖 C、C 又依赖 A，就会形成循环依赖。在构建系统中检测到环应立刻报错，因为这种情况下不存在任何合法的构建顺序。
defis_topological_order_unique(graph):
"""判断拓扑排序结果是否唯一 核心: Kahn算法执行过程中，队列中的元素始终不超过1个 """
indegree = [0] * graph.V
for u in range(graph.V):
for v in graph.adj[u]:
indegree[v] += 1
queue = deque([i for i in range(graph.V) if indegree[i] == 0])
if len(queue) > 1:
returnFalse# 初始阶段就有多个候选，结果不唯一while queue:
u = queue.popleft()
for v in graph.adj[u]:
indegree[v] -= 1if indegree[v] == 0:
queue.append(v)
if len(queue) > 1:
returnFalsereturnTrue
这个唯一性判定条件背后有深刻的图论意义。拓扑排序唯一当且仅当 DAG 中存在一条哈密顿路径（Hamiltonian Path），即经过每个顶点恰好一次的路径。但哈密顿路径的判定本身是 NP 完全的，而通过 Kahn 算法的运行过程来判定唯一性只需要 O(V+E) 的时间，是一个非常高效的工程实践方法。
import heapq
deflexicographical_topological_sort(graph):
"""字典序拓扑排序：使用最小堆替代普通队列 保证输出结果在所有合法拓扑序中字典序最小 """
indegree = [0] * graph.V
for u in range(graph.V):
for v in graph.adj[u]:
indegree[v] += 1# 使用最小堆替代普通队列
heap = [i for i in range(graph.V) if indegree[i] == 0]
heapq.heapify(heap)
result = []
while heap:
u = heapq.heappop(heap) # 总是弹出当前最小的顶点
result.append(u)
for v in graph.adj[u]:
indegree[v] -= 1if indegree[v] == 0:
heapq.heappush(heap, v)
if len(result) != graph.V:
returnNonereturn result
deffind_course_order(num_courses, prerequisites):
""" 根据先修关系返回课程修读顺序，使用字典序拓扑排序 Args: num_courses: 课程总数 prerequisites: 先修关系列表，[[a,b]] 表示修 a 必须先修 b Returns: list: 课程修读顺序，如无法完成则返回空列表 """# 构建邻接表
adj = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, prereq in prerequisites:
adj[prereq].append(course) # prereq -> course
indegree[course] += 1# 最小堆实现字典序
heap = [i for i in range(num_courses) if indegree[i] == 0]
heapq.heapify(heap)
order = []
while heap:
u = heapq.heappop(heap)
order.append(u)
for v in adj[u]:
indegree[v] -= 1if indegree[v] == 0:
heapq.heappush(heap, v)
return order if len(order) == num_courses else []
八、应用场景
拓扑排序的应用遍及计算机科学的各个领域。以下是最具有代表性的几个应用场景。
1. Makefile 构建系统
在软件工程中，Make 工具需要根据 Makefile 中定义的依赖关系确定源文件的编译顺序。目标文件（.o）依赖于源文件（.c 或 .cpp），可执行文件又依赖于目标文件。Make 使用拓扑排序确定构建顺序，确保每个文件在被使用之前都已正确编译。当 Make 检测到循环依赖时，它会报错并终止构建过程，这正是拓扑排序环检测功能在实践中的应用。
2. 包管理器依赖解析
Linux 的 apt、Python 的 pip、Node.js 的 npm、Rust 的 cargo 等包管理器，在安装软件包时都需要解析依赖关系图。假设包 A 依赖包 B，包 B 依赖包 C，包管理器必须按照 C→B→A 的顺序安装。一旦依赖图中出现环（A 依赖 B，B 依赖 A），包管理器必须通过版本回溯或拒绝安装来处理。
defresolve_package_dependencies(packages):
"""模拟包管理器依赖解析 packages: dict, {包名: [依赖列表]} """# 构建依赖图
name_to_id = {name: i for i, name in enumerate(packages)}
V = len(packages)
adj = [[] for _ in range(V)]
indegree = [0] * V
for name, deps in packages.items():
u = name_to_id[name]
for dep in deps:
v = name_to_id[dep]
adj[v].append(u) # dep -> name: 先安装依赖
indegree[u] += 1
queue = deque([i for i in range(V) if indegree[i] == 0])
install_order = []
while queue:
u = queue.popleft()
install_order.append([name for name, i in name_to_id.items() if i == u][0])
for v in adj[u]:
indegree[v] -= 1if indegree[v] == 0:
queue.append(v)
return install_order if len(install_order) == V elseNone
在大型项目中，编译器需要处理成千上万个源文件之间的依赖关系。模块 A 引用了模块 B 的头文件，那么 A 必须在 B 之后编译。编译器通过分析 #include 指令和模块导入语句来构建依赖图，然后使用拓扑排序确定编译顺序。合理的编译顺序可以最大化并行度（同时编译互不依赖的模块），从而显著减少整体编译时间。
5. 数据处理流水线
在数据工程中，ETL 管道（Extract-Transform-Load）的任务之间通常存在依赖关系——转换任务必须等待抽取任务完成，加载任务必须等待转换任务完成。Airflow、Luigi 等工作流调度系统使用 DAG 来建模这些依赖关系，并利用拓扑排序确定任务的执行顺序。当 Dag 中的某个任务失败时，其下游任务会被自动跳过或等待重试。
核心洞察：拓扑排序的应用本质上是将"依赖关系"这个抽象概念转化为具体的"执行顺序"。只要一个问题可以抽象为 DAG（节点 = 任务/实体，边 = 依赖关系），就可以运用拓扑排序来求解合理的处理顺序。识别问题的 DAG 结构是应用拓扑排序的关键第一步。
九、复杂度分析与优化
时间复杂度
无论是 Kahn 算法还是 DFS 后序法，时间复杂度都是 O(V+E)，其中 V 是顶点数，E 是边数。这是因为：
初始化入度表 / 颜色数组需要 O(V) 时间。
遍历所有边统计入度需要 O(E) 时间。
每个顶点恰好入队 / 入栈一次，每次出队 / 出栈需要 O(1) 时间（使用队列或栈时）。
每条边恰好被遍历一次（在 Kahn 算法中更新入度时，在 DFS 中访问邻居时）。
空间复杂度
空间复杂度为 O(V)，主要开销来自：
入度数组 indegree[] 占用 O(V) 空间。
队列或递归栈在最坏情况下占用 O(V) 空间。
结果列表占用 O(V) 空间。
图的邻接表本身占用 O(V+E) 空间，但这通常不计入算法辅助空间。
字典序版本的额外开销
当使用优先队列实现字典序拓扑排序时，时间复杂度退化为 O(V log V + E)，因为堆的每次插入和弹出操作都需要 O(log V) 时间。在顶点数巨大的情况下，如果不需要字典序约束，应优先使用普通队列。