有向图的拓扑排序python

在Python中，可以使用拓扑排序算法来对有向图进行拓扑排序。以下是一个实现拓扑排序的示例代码：

from collections import defaultdict

def topological_sort(graph):
    # 创建一个字典来存储每个顶点的入度
    in_degree = defaultdict(int)
    
    # 计算每个顶点的入度
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1
    
    # 创建一个队列，并将入度为0的顶点加入队列
    queue = []
    for node in graph:
        if in_degree[node] == 0:
            queue.append(node)
    
    # 进行拓扑排序
    result = []
    while queue:
        # 从队列中取出一个顶点
        node = queue.pop(0)
        result.append(node)
        
        # 将该顶点的所有邻居的入度减1，并将新的入度为0的顶点加入队列
        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

这段代码使用了一个字典来表示有向图，其中字典的键是顶点，值是与该顶点相连的邻居顶点的列表。函数 `topological_sort` 实现了拓扑排序算法，返回一个拓扑排序后的顶点列表。

你可以根据自己的需要构建一个有向图，并调用 `topological_sort` 函数进行拓扑排序。例如：

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

try:
    result = topological_sort(graph)
    print("拓扑排序结果:", result)
except ValueError as e:
    print(e)

输出结果为：

拓扑排序结果: ['A', 'C', 'B', 'D']

这表示拓扑排序后的顶点顺序为 A -> C -> B -> D。