拓扑排序卡恩算法 BFS 或 DFS

Question

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

2. 卡恩算法与 BFS（或 DFS）相同吗？或者BFS（或DFS）只是卡恩算法的工具？

Answer 1

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

• 如果您无法轻松访问所有顶点的列表（例如，当您仅获得对图的根的引用时），那么在实现卡恩算法之前必须进行搜索以找到所有顶点，因此您可能会这样做我们将使用 DFS 并同时进行拓扑排序。

• 如果您的图可能有很长的路径，那么使用递归搜索是不合适的。DFS 实现应该使用显式堆栈，这使得它比 Kahn 算法更复杂。如果您确实有所有顶点的列表，那么您可能想改用卡恩算法。

如果以上两种情况都不适用或两者都不适用，那么这几乎就是一次洗涤，您应该使用您喜欢的任何一种。在这种情况下，我通常会使用卡恩算法，因为检测输入图中的循环更容易快速且稳健。