使用BFS进行拓扑排序

• Z时代
• 2024-01-10
• 分类：问答

广度优先搜索可用于查找图形中的顶点和强连接的组件的拓扑排序吗？

如果是，该怎么做？如果不是，为什么呢？

我们通常会在这些问题中使用“深度优先”搜索，但是如果我尝试使用BFS进行实施，将会出现什么问题？

这样的代码行吗？

def top_bfs(start_node):
    queue = [start_node]
    stack = []
    while not queue.empty():
        node = queue.dequeue()
        if not node.visited:
            node.visited = True
            stack.push(node)
            for c in node.children:
                queue.enqueue(c) 
    stack.reverse()
    return stack

回答：

它们具有相似的名称这一事实并不会使它们具有相似的方法。

DFS通常是通过LIFO（如果需要的话，是一个堆栈）实现的-后进先出。

BFS通常使用FIFO（如果需要的话，是一个队列）实现-先进先出。

您可以按照任意方式遍历图，最终得出其节点的拓扑顺序。但是，如果您想高效地执行此操作，则DFS是最佳选择，因为节点的拓扑顺序实质上反映了它们在图中的深度（当然，“依赖深度”更为准确）。

以上是 使用BFS进行拓扑排序 的全部内容， 来源链接： utcz.com/qa/406802.html