拓扑排序算法

题目描述
给定一个有向无环图（DAG），将所有顶点排列成一个线性序列，使得对于图中任意一条有向边 (u, v)，在序列中顶点 u 都出现在顶点 v 的前面。这种顶点序列称为拓扑排序。请设计算法实现拓扑排序。

解题过程

拓扑排序的核心思想是基于顶点的入度（指向该顶点的边的数量）来逐步处理。我们将从入度为0的顶点开始，这些顶点不依赖于任何其他顶点，可以安全地放在序列的开头。

步骤1：理解基本概念

• 入度：指向某个顶点的边的数量
• 关键观察：DAG中至少存在一个入度为0的顶点，且拓扑排序序列可能不唯一

步骤2：算法思路（Kahn算法）

1. 计算每个顶点的入度
2. 将所有入度为0的顶点加入队列
3. 从队列中取出顶点，将其加入拓扑序列
4. 移除该顶点的所有出边，更新相邻顶点的入度
5. 如果某个相邻顶点的入度变为0，将其加入队列
6. 重复步骤3-5直到队列为空

步骤3：详细实现步骤

假设图有n个顶点，编号从0到n-1，使用邻接表表示：

def topological_sort(n, edges):
    # 构建邻接表和入度数组
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    
    # 初始化图和入度
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1
    
    # 找到所有入度为0的顶点
    queue = collections.deque()
    for i in range(n):
        if indegree[i] == 0:
            queue.append(i)
    
    # 执行拓扑排序
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        
        # 处理所有相邻顶点
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    
    # 检查是否有环
    if len(result) != n:
        return []  # 存在环，无法拓扑排序
    
    return result

步骤4：具体示例演示

考虑有向图：0→1→2，0→3

• 顶点0：入度=0
• 顶点1：入度=1（来自0）
• 顶点2：入度=1（来自1）
• 顶点3：入度=1（来自0）

执行过程：

1. 初始：队列=[0]，入度=[0,1,1,1]
2. 处理0：结果=[0]，更新顶点1,3的入度变为0,0，队列=[1,3]
3. 处理1：结果=[0,1]，更新顶点2入度变为0，队列=[3,2]
4. 处理3：结果=[0,1,3]，队列=[2]
5. 处理2：结果=[0,1,3,2]

得到拓扑序列：[0,1,3,2] 或 [0,3,1,2]（顺序可能不同但都有效）

步骤5：算法分析

• 时间复杂度：O(V+E)，其中V是顶点数，E是边数
• 空间复杂度：O(V)
• 应用场景：任务调度、课程安排、依赖关系解析等

步骤6：环检测
如果最终结果中的顶点数量不等于总顶点数，说明图中存在环，无法进行拓扑排序。这是判断DAG的重要方法。