algorithm - 拓扑搜索和广度优先搜索

Question

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

原因:BFS 在访问具有下一个深度值的节点之前访问特定深度中的所有节点。这自然意味着如果我们进行 BFS， parent 将列在 child 之前。这不正是我们需要的拓扑排序吗？

Answer 1

单纯的 BFS 仅对一棵树(或森林)足够，因为在(森林)树中，入度最多为 1。现在，看看这个案例:

B → C → D
      ↗
    A

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

顺便说一句，这是你的“理由”的缺陷:BFS 只保证之前访问过一位 parent ，而不是所有 parent 。

编辑:(*) 换句话说，你推回入度为零的相邻节点(在这个例子中，处理完A，D 将被跳过)。所以，您仍在使用队列，只是在通用算法中添加了一个过滤步骤。话虽这么说，继续称它为 BFS 是值得怀疑的。