Python中使用拓扑排序对有向图进行排序

from collections import deque

def topological_sort(graph):
    # 计算每个节点的入度
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    # 将入度为0的节点加入队列
    zero_in_degree_nodes = deque(node for node in in_degree if in_degree[node] == 0)

    # 记录排序后的节点顺序
    sorted_nodes = []

    # 依次将入度为0的节点弹出队列，并更新与之相邻节点的入度
    while zero_in_degree_nodes:
        node = zero_in_degree_nodes.popleft()
        sorted_nodes.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                zero_in_degree_nodes.append(neighbor)

    # 如果存在入度不为0的节点，说明存在环，无法进行拓扑排序
    if len(sorted_nodes) != len(graph):
        raise ValueError('存在环，无法进行拓扑排序')

    return sorted_nodes

# 构建有向图
graph = {
    'p': ['i', 'd', 'a', 'n', 'c', 'o', 'd', 'e', '.', 'c', 'o', 'm'],
    'i': ['d', 'a'],
    'd': ['a'],
    'n': ['s'],
    'e': ['r', 'o'],
    'r': ['o'],
    'o': ['m']
}

# 对有向图进行拓扑排序
sorted_nodes = topological_sort(graph)
print(sorted_nodes)  # 输出：['p', 'i', 'd', 'a', 'n', 'c', 'o', 'e', 'r', 'm', 's']