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

Question

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

Answer 1

我相信,你真正需要的是一个拓扑排序算法,如下所述:

http://en.wikipedia.org/wiki/Topological_sorting

如果有向图具有循环,则算法将失败.

我到目前为止看到的评论/回复似乎缺少一个事实,即在定向图可能有不止一种方法从节点X获得,而不存在图中的任何(导演)周期节点Y.

Answer 2

通常使用深度优先搜索. 我不知道BFS是否适用.

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

有关更详细的说明,请参见http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf.