对于无向图，如果我们需要找到一个循环，我们使用这个较早的问题中描述的深度优先搜索，这是一种众所周知的方法，也是最优的。
但是对于有向图，this other question建议使用拓扑排序。
我的问题是，为什么我们不能使用与无向图相同的技术来检查有向图中的循环？我考虑过各种情况，算法似乎总是一致的。
谁能提出一些示例有向图，其中 DFS 无法找到循环但拓扑排序可以？
问问题
4850 次
1 回答
9
您的问题似乎如下：您可以使用深度优先搜索来检测无向图中的循环，还是应该使用拓扑排序？
答案是这两种方法都行得通。如果有向图中存在循环，则可以通过在图上运行深度优先搜索来检测到这一点。只要您从循环中的一个节点开始搜索，就可以保证最终发现该循环。
事实证明，拓扑排序和 DFS 在以下方面密切相关：如果您在图中运行 DFS 并且没有找到循环，那么将每个节点标记为完全探索的相反顺序将给出拓扑图表之类的。换句话说，“使用拓扑排序”的解决方案和“使用DFS”的解决方案可以被认为是极其相似的算法，因为实现拓扑排序的一种方式是使用DFS。
希望这可以帮助！
于 2013-05-27T19:57:03.547 回答