拓扑排序python

在 Python 中实现拓扑排序可以通过使用深度优先搜索（DFS）算法来实现。下面是一个示例代码：

from collections import defaultdict

def dfs(graph, node, visited, result):
    visited.add(node)
    
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, result)
    
    result.append(node)

def topological_sort(graph):
    visited = set()
    result = []
    
    for node in graph:
        if node not in visited:
            dfs(graph, node, visited, result)
    
    result.reverse()
    return result

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

sorted_nodes = topological_sort(graph)
print(sorted_nodes)

输出结果为：`['A', 'C', 'B', 'D']`

在这个示例中，我们使用了一个有向无环图（DAG）作为输入。`graph` 是一个字典，其中键表示节点，值是一个列表，表示该节点的所有后继节点。`topological_sort` 函数通过调用 `dfs` 函数来执行深度优先搜索，并将访问过的节点添加到 `visited` 集合中，然后将其添加到 `result` 列表中。最后，我们使用 `result.reverse()` 将结果反转，得到拓扑排序的顺序。

请注意，这只是一个简单的示例，实际应用中可能需要处理更复杂的图结构和边界情况。