10.1 拓扑排序的定义
拓扑排序 是对有向无环图（DAG）顶点的线性排序，这样对于每条边 (u, v)，顶点 u 都在顶点 v 之前。这个排序只能用于 DAG，对于包含环的图无法完成。
有什么理解吗？如果你一看就懂，那估计你已经有不少算法经验了。
简单来说就是这样：你有一个任务列表（图的顶点）和任务之间的依赖关系（图中的箭头）。 任务的排序（顶点）要保证所有“任务 A”依赖的任务都在它之前完成。一下子就明了了，不然“有向无环图顶点的线性排序”这句话…
拓扑排序 是个非常重要的实践算法，所以它有个专属名字，而不只是某个作者的名字。 让我们来看看在哪些地方用得上这个算法：
应用场景：
1. 任务调度 (Task Scheduling)：
确定依赖任务的执行顺序，以便每个任务都在它所有的依赖任务完成之后执行。
示例：
在项目管理系统中规划项目。
2. 代码编译：
确定彼此依赖的模块或源码文件的编译顺序。
示例：
在构建系统中优化软件构建（例如，Makefile）。
3. 包管理器中的依赖解析：
对包进行排序，以确保在安装包本身之前安装所有依赖。
示例：
简化在包管理器（例如，npm，pip，apt）中的软件安装过程。
4. 路线优化：
在考虑它们之间的依赖关系的前提下，确定访问点或执行操作的顺序。
示例：
物流和配送路线规划。
拓扑排序的时间和空间复杂度：
时间复杂度：
两种主要的拓扑排序算法（DFS 和 Kahn 算法）的时间复杂度都是 O(V + E)，其中 V 是顶点数量，E 是图中的边的数量。
空间复杂度：
两种算法的空间复杂度均为 O(V + E)，因为需要存储图，以及用于跟踪已访问顶点和前驱的数组。
10.2 深度优先搜索（DFS）实现
拓扑排序可以通过多种方式实现，其中一种是基于深度优先搜索 — DFS。DFS 算法使用栈来跟踪已完成的节点。
实现示例：
def topological_sort_dfs(graph):
def dfs(vertex, visited, stack):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(neighbor, visited, stack)
stack.append(vertex)
visited = set()
stack = []
for vertex in graph:
if vertex not in visited:
dfs(vertex, visited, stack)
return stack[::-1] # 结果以相反顺序返回
# 使用示例：
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_dfs(graph)
print("拓扑排序:", result)
输出：
拓扑排序: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']
10.3 实现：Kahn 算法
另一种方法称为 Kahn 算法。Kahn 算法使用顶点的入度概念来进行拓扑排序。
实现示例：
from collections import deque, defaultdict
def topological_sort_kahn(graph):
in_degree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_degree[v] += 1
queue = deque([u for u in graph if in_degree[u] == 0])
top_order = []
while queue:
u = queue.popleft()
top_order.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(top_order) == len(in_degree):
return top_order
else:
raise ValueError("图中含有环")
# 使用示例：
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_kahn(graph)
print("拓扑排序:", result)
输出：
拓扑排序: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']
GO TO FULL VERSION