唯一拓扑排序怎么实现

唯一拓扑排序是指在有向无环图（DAG）中，对所有的顶点进行排序，使得对于任意一对顶点u和v，如果存在一条从u到v的路径，那么在排序中u一定在v的前面。实现唯一拓扑排序的一种常见方法是使用深度优先搜索（DFS）和拓扑排序算法。

下面是一个使用DFS和拓扑排序算法实现唯一拓扑排序的示例代码：

def topological_sort(graph):
    visited = set()
    stack = []

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

    for node in graph:
        if node not in visited:
            dfs(node)

    return stack[::-1]

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

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

在这个示例中，我们首先定义了一个`topological_sort`函数，它接受一个有向图作为输入，并返回一个唯一拓扑排序的列表。然后，我们使用深度优先搜索算法来遍历图中的所有节点，并将访问过的节点添加到`visited`集合中。在每次访问一个节点时，我们递归地访问它的邻居节点，直到没有未访问的邻居节点为止。最后，我们将访问过的节点按照逆序添加到`stack`列表中，即得到了唯一拓扑排序的结果。