拓扑排序 Kahn 算法 BFS 或 DFS。

Question

1. 拓扑排序的方法是BFS还是DFS，哪个是正确的？
   （我认为BFS是正确的，但有些网站说DFS和BFS也有人说。我很困惑...）

2. Kahn算法和BFS（或DFS）相同吗？还是BFS（或DFS）只是Kahn算法的工具？

- ywbird

---

拓扑排序可以用两种方式完成，但像BFS一样完成可能更好/更简单/更有效。如果我没记错的话，Kahn算法实际上就是BFS。 - RBarryYoung

Kahn算法与BFS无关。 - Matt Timmermans

@RBarryYoung，如果我正确理解Wikipedia文章，那么它说，“结构S可以简单地是一个集合、队列或栈”；所以我认为可以使用DFS（通过使用堆栈）来实现Kahn算法。你同意吗？我有什么遗漏吗？ - Someone

Answer 1

Kahn算法和DFS都可以用于实践中的拓扑排序。选择哪一个取决于您的图形及其表示方式：

• 如果您没有轻松访问所有顶点的列表（例如，当您仅获得对图的根的引用时），则在实现Kahn算法之前必须搜索所有顶点，因此您可能想使用DFS同时进行拓扑排序。

• 如果您的图形可能具有长路径，则不适宜使用递归搜索。DFS实现应使用显式堆栈，这使其比Kahn算法更复杂。如果您确实有所有顶点的列表，则可能要改用Kahn算法。

如果上述选项均不适用或均适用，则两种方法差别不大，您可以使用喜欢的那一种。在这种情况下，我通常使用Kahn算法，因为检测输入图中的循环更容易使其快速且健壮。

- Matt Timmermans