如何检测有向图是循环的？ [英] How to detect if a directed graph is cyclic?

问题描述

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

解决方案

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

在 DFS ，生成树是按访问顺序构建的。如果树中的节点的祖先被访问（即创建了一个后沿），那么我们检测到一个循环。

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

How can we detect if a directed graph is cyclic? I thought using breadth first search, but I'm not sure. Any ideas?

解决方案

Usually depth-first search is used instead. I don't know if BFS is applicable easily.

In DFS, a spanning tree is built in order of visiting. If a the ancestor of a node in the tree is visited (i.e. a back-edge is created), then we detect a cycle.

See http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf for a more detailed explanation.

这篇关于如何检测有向图是循环的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！