python拓扑排序

拓扑排序是一种对有向无环图（DAG）进行排序的算法。在 Python 中，可以使用拓扑排序来解决依赖关系的问题，如任务调度、编译器优化等。

以下是一个使用拓扑排序算法的示例代码：

from collections import defaultdict

def topological_sort(graph):
    # 用于存储顶点的入度
    in_degree = defaultdict(int)
    # 用于存储每个顶点的后继顶点
    successors = defaultdict(list)
    
    # 统计每个顶点的入度和后继顶点
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
            successors[u].append(v)
    
    # 初始化一个队列，用于存储入度为0的顶点
    queue = []
    for u in graph:
        if in_degree[u] == 0:
            queue.append(u)
    
    # 拓扑排序的结果
    result = []
    
    # 开始拓扑排序
    while queue:
        u = queue.pop(0)
        result.append(u)
        
        # 将 u 的后继顶点的入度减1，如果入度为0，则加入队列
        for v in successors[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    # 如果图中有环，说明无法进行拓扑排序
    if len(result) != len(graph):
        raise ValueError("The graph contains a cycle")
    
    return result

使用示例：

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

result = topological_sort(graph)
print(result)  # 输出：['A', 'C', 'B', 'D']

在以上示例中，我们定义了一个有向图 `graph`，然后调用 `topological_sort` 函数进行拓扑排序。最后输出的结果就是拓扑排序的顺序。这里的结果是 `['A', 'C', 'B', 'D']`，表示先完成顶点 A，然后是 C，接着是 B，最后是 D。