拓扑搜索和广度优先搜索 [英] Topological search and Breadth first search

问题描述

是否有可能使用广度优先搜索逻辑做一个拓扑排序的DAG？ 在Cormen溶液利用深度优先搜索，但不会是更容易使用的BFS？

Is it possible to use Breadth first search logic to do a topological sort of a DAG? The solution in Cormen makes use of Depth first search but wouldn't be easier to use BFS?

原因： BFS访问一个特定深度的所有节点访问节点的下一个深度值之前。这自然意味着如果我们做一个BFS的父母将上市前的孩子。这不正是我们所需要的拓扑排序？

Reason: BFS visits all the nodes in a particular depth before visiting nodes with the next depth value. It naturally means that the parents will be listed before the children if we do a BFS. Isn't this exactly what we need for a topological sort?

推荐答案

在一个BFS你居然走最终会在正确的方向上的边缘。但是，所有的边缘，你不走（这些节点之间在同一深度，或来自更深层次的节点回升到先前节点）将最终去了错误的方式，如果你布置图的BFS顺序。

In a BFS all of the edges you actually walk will end up in the correct direction. But all the edges you don't walk (those between nodes at the same depth, or those from deeper nodes back up to earlier nodes) will end up going the wrong way if you lay out the graph in BFS order.

是的，你真的需要DFS做到这一点。

Yes, you really need DFS to do it.

这篇关于拓扑搜索和广度优先搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！