拓扑排序

拓扑排序（Topological Sorting）是有向无环图（DAG, Directed Acyclic Graph）中顶点的一种线性排序，使得对于图中的每一条有向边 $(u,v)$，顶点 $u$ 在排序中总是位于顶点 $v$ 的前面。拓扑排序常用于解决依赖关系问题，例如任务调度、课程安排或编译顺序确定等场景。

基本概念

拓扑排序的核心思想是：

• 仅适用于有向无环图（DAG），若图中存在环，则无法进行拓扑排序。
• 排序结果不唯一，可能存在多种合法的拓扑序列。
• 通常通过深度优先搜索（DFS）或广度优先搜索（BFS，Kahn算法）实现。

算法步骤（Kahn算法）

1. 计算所有顶点的入度（即指向该顶点的边数）。 2. 将入度为0的顶点加入队列。 3. 依次取出队列中的顶点，并将其输出到拓扑序列中。 4. 将该顶点的所有邻接顶点的入度减1，若减后入度为0，则加入队列。 5. 重复步骤3-4，直到队列为空。若输出的顶点数等于图中顶点总数，则排序成功；否则说明图中存在环。

示例图

graph LR A --> B A --> C B --> D C --> D D --> E

• 可能的拓扑排序结果：A → B → C → D → E 或 A → C → B → D → E。

代码实现

以下是基于Kahn算法的Python实现：

  
from collections import deque  

def topological_sort(graph):  
    # 计算所有顶点的入度  
    in_degree = {u: 0 for u in graph}  
    for u in graph:  
        for v in graph[u]:  
            in_degree[v] += 1  

    # 初始化队列（入度为0的顶点）  
    queue = deque([u for u in in_degree if in_degree[u] == 0])  
    topo_order = []  

    while queue:  
        u = queue.popleft()  
        topo_order.append(u)  
        # 遍历邻接顶点，减少其入度  
        for v in graph[u]:  
            in_degree[v] -= 1  
            if in_degree[v] == 0:  
                queue.append(v)  

    if len(topo_order) == len(graph):  
        return topo_order  
    else:  
        return []  # 存在环，无法排序  

# 示例输入（邻接表表示）  
graph = {  
    'A': ['B', 'C'],  
    'B': ['D'],  
    'C': ['D'],  
    'D': ['E'],  
    'E': []  
}  

print(topological_sort(graph))  # 输出: ['A', 'B', 'C', 'D', 'E']

实际应用

1. 任务调度：如构建系统中确定编译顺序（例如Makefile）。 2. 课程安排：根据课程依赖关系（先修课）生成学习计划。 3. 数据流分析：在编译器优化中确定指令执行顺序。

案例：课程表问题

问题描述：给定课程总数 $n$ 和依赖列表 $[[a,b],...]$（表示课程 $a$ 依赖 $b$），判断是否能完成所有课程。

  
def can_finish(num_courses, prerequisites):  
    graph = {i: [] for i in range(num_courses)}  
    in_degree = {i: 0 for i in range(num_courses)}  
    for a, b in prerequisites:  
        graph[b].append(a)  
        in_degree[a] += 1  

    queue = deque([i for i in in_degree if in_degree[i] == 0])  
    count = 0  
    while queue:  
        u = queue.popleft()  
        count += 1  
        for v in graph[u]:  
            in_degree[v] -= 1  
            if in_degree[v] == 0:  
                queue.append(v)  
    return count == num_courses  

print(can_finish(2, [[1, 0]]))  # 输出: True

复杂度分析

• 时间复杂度：$O(V+E)$（$V$为顶点数，$E$为边数）。
• 空间复杂度：$O(V)$（存储入度和队列）。

常见问题

• 如何处理环？：若拓扑序列的顶点数少于图中顶点总数，则说明存在环。
• 为何使用队列？：队列保证了入度为0的顶点按顺序处理，但也可以用栈实现逆序排序。

扩展阅读

• 深度优先搜索（DFS）实现的拓扑排序。
• 动态规划与拓扑排序的结合（如最长路径问题）。