graph - 如何检测有向图是否循环？

Question

我们如何检测有向图是否是循环的？我想使用广度优先搜索，但我不确定。有任何想法吗？

Answer 1

通常使用深度优先搜索来代替。不知道BFS好不好用。

在 DFS ，生成树是按照访问顺序构建的。如果访问了树中节点的祖先(即创建了后边缘)，则我们检测到一个循环。

见 http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf以获得更详细的解释。