拓扑排序（Topological Sorting）原理与实现

拓扑排序是一种针对有向无环图（DAG）的线性排序算法。该排序将图中的所有顶点排成一个序列，使得对于任何一条从顶点 \(u\) 到顶点 \(v\) 的有向边 \(u \to v\)，在排序序列中 \(u\) 都出现在 \(v\) 的前面。拓扑排序常用于解决具有依赖关系的问题，例如任务调度、编译顺序等。

一、问题描述与关键概念

• 输入：一个有向无环图（DAG），包含若干顶点和边。
• 输出：顶点的一个拓扑序列（可能不唯一），满足所有边的方向性要求。
• 关键概念：
  • 入度（In-degree）：指向某顶点的边的数量。
  • 出度（Out-degree）：从某顶点指出的边的数量。
  • DAG 的性质：无环保证了拓扑排序的存在性（有环图无法进行拓扑排序）。

二、拓扑排序的算法步骤（基于 Kahn 算法）
Kahn 算法是一种基于入度的广度优先搜索（BFS）方法，步骤如下：

1. 初始化：

   • 计算图中每个顶点的入度，保存到数组 inDegree 中。
   • 初始化一个队列（或栈），用于存放入度为 0 的顶点。
   • 初始化一个空列表 result，用于存储拓扑序列。

2. 处理入度为 0 的顶点：

   • 遍历所有顶点，将入度为 0 的顶点加入队列。

3. 循环处理队列：

   • 从队列中取出一个顶点 \(u\)，将其加入 result。
   • 遍历 \(u\) 的所有邻接顶点 \(v\)：
     • 将 \(v\) 的入度减 1（相当于移除边 \(u \to v\)）。
     • 如果 \(v\) 的入度变为 0，将 \(v\) 加入队列。
   • 重复直到队列为空。

4. 检查结果：

   • 如果 result 包含的顶点数等于图中顶点总数，说明拓扑排序成功。
   • 否则，说明图中存在环，无法完成拓扑排序。

三、具体示例
以顶点集 {A, B, C, D} 和边集 {A→B, A→C, B→D, C→D} 为例：

1. 初始入度：A:0, B:1, C:1, D:2。
2. 队列初始化为 [A]（入度为 0）。
3. 处理 A：
   • result = [A]
   • 更新 B 和 C 的入度（均减 1），入度变为 B:0, C:0。将 B、C 加入队列。
4. 处理 B：
   • result = [A, B]
   • 更新 D 的入度（减 1），入度变为 D:1。队列剩余 [C]。
5. 处理 C：
   • result = [A, B, C]
   • 更新 D 的入度（减 1），入度变为 D:0。将 D 加入队列。
6. 处理 D：
   • result = [A, B, C, D]（排序完成）。

四、代码实现（Python）

from collections import deque

def topological_sort(vertices, edges):
    # 构建邻接表和入度数组
    graph = {v: [] for v in vertices}
    in_degree = {v: 0 for v in vertices}
    
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    # 初始化队列
    queue = deque([v for v in vertices if in_degree[v] == 0])
    result = []
    
    # BFS 处理
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    # 检查是否有环
    if len(result) != len(vertices):
        return None  # 存在环，排序失败
    return result

# 示例调用
vertices = ['A', 'B', 'C', 'D']
edges = [('A','B'), ('A','C'), ('B','D'), ('C','D')]
print(topological_sort(vertices, edges))  # 输出: ['A','B','C','D'] 或 ['A','C','B','D']

五、应用场景

1. 任务调度：如课程选修顺序、构建系统的编译顺序。
2. 依赖解析：软件包管理（如 apt-get）、数据管道处理。
3. 死锁检测：通过拓扑排序判断资源分配图是否存在环。

六、复杂度分析

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