拓扑搜索和广度优先搜索

Question

是否可以使用广度优先搜索逻辑来进行拓扑排序的DAG？Cormen的解决方案使用深度优先搜索,但使用BFS会更容易吗？

原因:BFS在访问具有下一个深度值的节点之前访问特定深度的所有节点.这自然意味着如果我们做BFS,父母将被列在孩子面前.这不是我们拓扑排序所需要的吗？

Answer 1

仅仅BFS对于树木(或树林)来说就足够了,因为在(森林)树木中,度数最多为1.现在,看看这种情况:

B ? C ? D
      ?
    A

队列初始化为A B(其度数为零)的BFS 将返回A B D C,这不是拓扑排序的.这就是为什么你必须保持in-degrees计数,并且只选择计数已降至零的节点.(*)

顺便说一句,这是你的"理由"的缺陷:BFS只保证以前访问过一个父母,而不是所有父母.

编辑:(*)换句话说,你推回其入度为零的相邻节点(例如,在处理之后A,D将跳过).所以,你仍在使用队列,你刚刚为通用算法添加了一个过滤步骤.话虽如此,继续称之为BFS是值得怀疑的.

Answer 2

甚至维基百科也有可能描述一种基于BFS的算法.

基本上,您使用一个队列,在该队列中插入没有传入边的所有节点.然后,当您提取节点时,将删除其所有传出边并插入可从其访问的节点,这些节点没有其他传入边.

Answer 3

在 BFS 中，你实际行走的所有边缘最终都会朝着正确的方向。但是，如果您按照 BFS 顺序布置图形，所有您不走的边（相同深度的节点之间的边，或者从较深的节点返回到较早的节点的边）最终都会走错路。

是的，你确实需要 DFS 来做到这一点。