图的拓扑排序算法

题目描述：
给定一个有向无环图（DAG），拓扑排序是将图中的所有顶点排成一个线性序列，使得对于图中的每一条有向边 \(u \to v\)，在序列中顶点 \(u\) 都出现在顶点 \(v\) 之前。拓扑排序常用于任务调度、依赖关系分析等场景。请实现图的拓扑排序算法。

解题过程循序渐进讲解：

步骤1：理解问题与数据结构

• 图由顶点（Vertex）和边（Edge）组成，有向边表示顶点间的依赖关系（例如 \(u \to v\) 表示 \(u\) 必须在 \(v\) 之前）。
• 常见表示方法：
  • 邻接表：为每个顶点维护一个列表，存储其指向的所有邻接顶点。空间复杂度 \(O(V+E)\)，适合稀疏图。
  • 邻接矩阵：二维数组记录边，空间 \(O(V^2)\)，适合稠密图。
• 拓扑排序的前提是无环，有环图无法进行拓扑排序（因为存在循环依赖）。

步骤2：核心思想

• 拓扑排序本质上是不断移除入度为0的顶点的过程。入度（in-degree）指指向该顶点的边的数量。
• 算法步骤：
  1. 统计每个顶点的入度。
  2. 将入度为0的顶点加入队列。
  3. 从队列中取出顶点，输出到结果序列，并“删除”该顶点及其出边（即将其邻接顶点的入度减1）。
  4. 若邻接顶点入度变为0，则加入队列。
  5. 重复直到队列为空。如果结果序列包含所有顶点，则排序成功；否则说明图中有环。

步骤3：详细算法流程（以邻接表为例）
假设图有 \(n\) 个顶点，编号从 \(0\) 到 \(n-1\)。

1. 初始化：
   • 创建入度数组 indegree[n]，初始为0。
   • 遍历所有边，对每条边 \(u \to v\)，令 indegree[v]++。
   • 创建队列（或栈），将所有入度为0的顶点入队。
2. 循环处理队列：
   • 弹出队首顶点 u，将 u 加入结果列表。
   • 遍历 u 的所有邻接顶点 v：
     • 将 indegree[v]--。
     • 如果 indegree[v] == 0，将 v 入队。
3. 结束判断：
   • 如果结果列表长度等于 \(n\)，则拓扑排序成功。
   • 如果小于 \(n\)，说明图中存在环，无法完成排序。

步骤4：示例演示
考虑下图（顶点数4，边：0→1, 0→2, 1→3, 2→3）：

0 → 1 → 3
 ↘  ↗
  2

• 初始化入度：indegree = [0, 1, 1, 2]（顶点3有两条入边）。
• 入度为0的顶点：0，入队。
• 处理队列：
  • 弹出0，结果 [0]，更新邻接顶点1和2的入度：indegree = [0, 0, 0, 2]，顶点1和2入度变为0，入队。
  • 弹出1，结果 [0,1]，更新顶点3入度：indegree[3]=1，入度不为0。
  • 弹出2，结果 [0,1,2]，更新顶点3入度：indegree[3]=0，入队。
  • 弹出3，结果 [0,1,2,3]。
• 结果长度为4，排序成功。可能的拓扑序列：[0,1,2,3] 或 [0,2,1,3]（不唯一）。

步骤5：代码实现（Python示例）

from collections import deque, defaultdict

def topological_sort(n, edges):
    # 构建邻接表和入度数组
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1
    
    # 初始化队列
    queue = deque([i for i in range(n) if indegree[i] == 0])
    result = []
    
    # BFS处理
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    
    # 检查是否有环
    if len(result) == n:
        return result
    else:
        return []  # 有环，返回空列表

# 示例调用
n = 4
edges = [(0,1), (0,2), (1,3), (2,3)]
print(topological_sort(n, edges))  # 输出：[0,1,2,3] 或类似

步骤6：复杂度与扩展

• 时间复杂度：\(O(V+E)\)，每个顶点和边各访问一次。
• 空间复杂度：\(O(V+E)\) 存储图，\(O(V)\) 存储入度和队列。
• 扩展讨论：
  • 如果要求所有可能的拓扑序列，需要用回溯法尝试所有顺序。
  • 拓扑排序也可用DFS实现：以深度优先顺序遍历，在顶点递归完成后逆序加入结果（需检测环）。
  • 应用场景：课程安排、编译顺序、任务调度等依赖问题。