是否可以使用广度优先搜索逻辑对 DAG 进行拓扑排序? Cormen 中的解决方案使用了深度优先搜索,但使用 BFS 不是更容易吗?
原因: BFS 在访问具有下一个深度值的节点之前访问特定深度中的所有节点。这自然意味着如果我们进行 BFS, parent 将列在 child 之前。这不正是我们需要的拓扑排序吗?
最佳答案
单纯的 BFS 仅对一棵树(或森林)足够,因为在(森林)树中,入度最多为 1。 现在,看看这个案例:
B → C → D
↗
A
队列初始化为 A B
(其入度为零)的 BFS 将返回 A B D C
,这不是拓扑排序的。这就是为什么您必须保持入度计数,并且只选择计数已降至零的节点。 (*)
顺便说一句,这是你的“理由”的缺陷:BFS 只保证之前访问过一位 parent ,而不是所有 parent 。
编辑:(*) 换句话说,你推回入度为零的相邻节点(在这个例子中,处理完A
,D
将被跳过)。所以,您仍在使用队列,只是在通用算法中添加了一个过滤步骤。话虽这么说,继续称它为 BFS 是值得怀疑的。
关于algorithm - 拓扑搜索和广度优先搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14906533/