使用BFS进行拓扑排序 [英] Using BFS for topological sort

问题描述

是否可以使用广度优先搜索来查找图形中的顶点和强连接的组件的拓扑排序？

Can Breadth first Search be used for finding topological sorting of vertices and strongly connected components in a graph?

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

If yes how to do that? and If not why not?

在这些问题中，我们通常使用深度优先搜索，但是如果我尝试使用BFS来实现，会有什么问题呢？

we generally use Depth first search in these problems but What will be the problem if I try to implement using BFS?

代码是否会像这样工作？

Will code like this work?

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

推荐答案

它们具有相似名称的事实并不能说明

The fact that they have similar names doesn't make them similar methods.

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

DFS is typically implemented with LIFO (a stack if you will) - last in first out.

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

BFS typically implemented with FIFO (a queue if you will) - first in first out.

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

You can walk a graph in any way you want, and eventually come out with a topological order of its nodes. But if you want to do it efficiently, then DFS is the best option, as the topological order of the nodes essentially reflects their depth in the graph (well, "dependency-depth" to be more accurate).

这篇关于使用BFS进行拓扑排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！