dfs和拓扑排序有区别吗？不使用dfs可以实现拓扑排序吗？

Question

我试图编写代码来检测有向图中的循环，如果没有循环，则返回相同的拓扑顺序。

在寻找它时，我遇到了不同的技术，例如 DFS 和拓扑排序来检测有向图中的循环。

这两者有什么区别吗？

Answer 1

拓扑排序是有向无环图的节点的特定顺序，可以通过深度优先搜索来计算。除了深度优先搜索之外，还有其他方法来查找拓扑顺序，例如Kahn 算法。

请注意，DAG 可能有许多有效的拓扑顺序（不限于一个）。这意味着 DFS 的一种实现可以产生一个（有效）顺序，而另一种 DFS 实现（其中通过不同的启发式选择节点）可以产生另一种顺序。

Answer 2

拓扑排序是有向无环图（DAG）上基于 DFS 的算法。拓扑排序是顶点的线性排序，使得对于每个有向边 uv，顶点 u 在排序中位于 v 之前。

当且仅当图没有有向环时，拓扑排序才是可能的。但 DFS 可以在有向图或无向图上执行。

Answer 3

拓扑排序按以下方式使用 DFS：

1. 致电DFS
2. 注意何时探索完所有边缘（即精加工 次）
3. 一个顶点完成后，在头部插入一个标识符 拓扑排序 L
4. 完成的列表L是一个拓扑排序

运行时间：O(V+E)

本质上，拓扑排序算法在 DAG 上使用 DFS。 DFS 属性对于返回的列表以正确的拓扑顺序显示至关重要。然而，正如上面的答案所示，如果不使用 DFS，就无法实现yes排序。例如Kahn 算法 和并行排序。

Answer 4

如果你想清楚，可以尝试下面的问题。

https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&category=0&problem=1246&mosmsg=Submission+received+with+ID+25820106

起初，您可能会直接进行直接 DFS，但在某些情况下会失败。

例如：DFS 在以下测试用例中失败：

5 4（分别为顶点数和边数）

（边缘描述）

1 2

2 3

1 4

4 3