为什么在无向图中使用深度优先搜索查找环，而在有向图中使用拓扑排序查找环？

Question

对于无向图，如果我们需要查找环，我们使用深度优先搜索，如这个旧问题所述，这是一种众所周知的方法，也是最优的。

但是对于有向图，这个其他问题建议使用拓扑排序。

我的问题是，为什么我们不能使用与无向图相同的技术，在有向图中检查循环？我已经考虑了各种情况，算法似乎总是一致的。

有人能否提供一些示例有向图，在其中DFS无法找到循环，但拓扑排序可以？

- Spandan

---

顺便提一下，拓扑排序是通过执行深度优先搜索来实现的（也可能有其他方法）。因此，在这种情况下，将它们视为相同。 - Deep

Answer 1

似乎您的问题是：在无向图中，您是否可以使用深度优先搜索来检测循环，还是应该使用拓扑排序？

答案是两种方法都可以。如果有一个有向图中有一个循环，则可以通过对图运行深度优先搜索来检测到此循环。只要您从循环中的节点开始搜索，就保证最终会发现循环。

事实证明，拓扑排序和DFS密切相关，具体如下：如果在图中运行DFS并且没有找到循环，则将每个节点标记为完全探索的相反顺序将给出图的拓扑排序。换句话说，“使用拓扑排序”的解决方案和“使用DFS”的解决方案可以被认为是极其相似的算法，因为一种实现拓扑排序的方法是使用DFS。

希望这可以帮助您！

- templatetypedef

---

谢谢！解释得非常清楚。 - Spandan

抱歉在旧帖子上发布。但我有一个困惑。我们能否通过对图进行拓扑排序来检测循环？我认为答案是否定的，因为即使图中有一些循环，如果我们采用基于dfs的方法，拓扑排序仍然是可能的。 - Patel Parth

一个有环的有向图无法进行拓扑排序，因为无法将每个节点按照其前驱或后继节点的顺序排列。基于深度优先搜索的算法可以通过一些修改来检测这种情况 - 只需要跟踪当前正在探索但尚未完成的节点，并在尝试扩展其中一个节点时报告错误即可。 - templatetypedef

一个有环的有向图仍然可以进行拓扑排序。你可以比较已处理节点数和总节点数的数量。如果它们相同，则没有环。否则，存在环。 - Alfred

@Alfred 有向图的拓扑排序是指每个节点出现在所有具有边缘的节点之后。如果存在环，则无法进行这样的排序。 - templatetypedef

如果节点没有边，您应该终止循环并比较“已处理节点”和“总节点”。 - Alfred