拓扑排序算法

题目描述：给定一个有向无环图（DAG），包含n个节点（编号从0到n-1）和若干条有向边，要求生成该图的一个拓扑排序。拓扑排序是指对图中所有节点的一个线性排列，使得对于图中的每一条有向边(u → v)，在排序中节点u都出现在节点v之前。

解题过程：

1. 理解拓扑排序的核心概念
   拓扑排序只适用于有向无环图（DAG），如果图中存在环，则无法进行拓扑排序。拓扑排序的实际意义可以理解为任务之间的依赖关系，比如课程先修关系、任务执行顺序等。

2. 算法实现思路
   我们使用Kahn算法（基于BFS的拓扑排序）：

• 计算每个节点的入度（指向该节点的边的数量）
• 将所有入度为0的节点加入队列
• 依次处理队列中的节点，将其邻居节点的入度减1
• 如果邻居节点入度变为0，则加入队列
• 记录出队顺序即为拓扑排序

3. 详细步骤分解

步骤1：初始化数据结构

# 构建邻接表表示图
graph = [[] for _ in range(n)]
# 记录每个节点的入度
in_degree = [0] * n

步骤2：构建图和计算入度
对于每条边(u → v)：

• 将v添加到u的邻接表中
• 将v的入度加1

步骤3：初始化队列

from collections import deque
queue = deque()
# 将所有入度为0的节点加入队列
for i in range(n):
    if in_degree[i] == 0:
        queue.append(i)

步骤4：执行拓扑排序

topo_order = []
while queue:
    node = queue.popleft()
    topo_order.append(node)
    
    # 遍历当前节点的所有邻居
    for neighbor in graph[node]:
        # 将邻居节点的入度减1
        in_degree[neighbor] -= 1
        # 如果邻居节点入度变为0，加入队列
        if in_degree[neighbor] == 0:
            queue.append(neighbor)

步骤5：验证结果
检查拓扑排序结果的长度：

• 如果长度等于n，说明排序成功
• 如果长度小于n，说明图中存在环，无法进行拓扑排序

4. 完整代码示例

from collections import deque

def topological_sort(n, edges):
    # 初始化
    graph = [[] for _ in range(n)]
    in_degree = [0] * n
    
    # 构建图
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    # 拓扑排序
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return result if len(result) == n else []  # 如果存在环返回空列表

5. 算法复杂度分析

• 时间复杂度：O(n + e)，其中n是节点数，e是边数
• 空间复杂度：O(n)，用于存储入度数组和队列

这个算法保证了在有向无环图中能够找到合理的节点执行顺序，是解决依赖关系问题的经典方法。