拓扑排序python算法

拓扑排序是对有向无环图进行排序的一种算法，它可以找到一种满足所有任务依赖关系的顺序。在Python中，可以使用collections模块中的deque来实现拓扑排序算法。具体实现步骤如下：

1. 统计每个顶点的入度，即每个顶点有多少个前驱节点。
2. 将入度为0的顶点加入队列。
3. 从队列中取出一个顶点，将其加入结果列表中，并移除该顶点及其相关边。
4. 对于该顶点的所有后继节点，将其入度减1，如果入度为0，则将其加入队列。
5. 重复步骤3和4，直到队列为空。
6. 如果结果列表的长度不等于图中顶点的个数，则说明图中存在环，无法进行拓扑排序。

下面是一个示例代码，实现了对一个有向无环图进行拓扑排序：

from collections import deque

def topological_sort(graph):
    # 统计每个顶点的入度
    in_degree = {v: 0 for v in graph}
    for v in graph:
        for neighbor in graph[v]:
            in_degree[neighbor] += 1
    
    # 将入度为0的顶点加入队列
    queue = deque([v for v in graph if in_degree[v] == 0])
    
    # 保存拓扑排序的结果
    result = []
    while queue:
        # 取出队列中的顶点
        v = queue.popleft()
        result.append(v)
        
        # 移除顶点及其相关边
        for neighbor in graph[v]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # 判断是否存在环
    if len(result) != len(graph):
        raise ValueError("图中存在环，无法进行拓扑排序。")
    
    return result

# 测试
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D', 'E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}
try:
    result = topological_sort(graph)
    print("拓扑排序结果:", result)
except ValueError as e:
    print(e)