拓扑排序

拓扑排序是对有向无环图（DAG）的节点进行排序，使得所有边都从前面的节点指向后面的节点。

Kahn 算法

概述

Kahn 算法使用队列进行拓扑排序，基于入度计算。

实现

from collections import deque

def topological_sort_kahn(graph):
    # 计算入度
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    # 初始化队列
    queue = deque([node for node in in_degree if in_degree[node] == 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)
    
    # 检查是否有环
    if len(result) != len(graph):
        raise ValueError("图中存在环")
    
    return result

# 示例图
dag = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}

print("Kahn 拓扑排序:", topological_sort_kahn(dag))

DFS 方法

概述

使用深度优先搜索进行拓扑排序。

实现

def topological_sort_dfs(graph):
    visited = set()
    stack = []
    
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return stack[::-1]

# 示例
print("DFS 拓扑排序:", topological_sort_dfs(dag))

复杂度分析

算法	时间复杂度	空间复杂度
Kahn	O(V + E)	O(V)
DFS	O(V + E)	O(V)

应用场景

• 任务调度
• 课程安排
• 依赖解析