algorithm - 拓扑排序 Kahn 算法 BFS 或 DFS

Question

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

2. Kahn 的算法是否与 BFS(或 DFS)相同？还是 BFS(或 DFS)只是 Kahn 算法的工具？

Answer 1

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

• 如果您无法轻松访问所有顶点的列表(例如，当您仅获得对图的根的引用时)，则必须在实现 Kahn 之前进行搜索以找到所有顶点算法，因此您不妨同时使用 DFS 和进行拓扑排序。

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

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