我知道这个问题有很多答案。然而，我发现他们中没有一个人真正把它讲到重点。
有些人认为循环(几乎)与强连通分量(s. Finding all cycles in a directed graph )相同，因此可以使用为该目标设计的算法。
有人争辩说，发现 循环可以通过 DFS 完成并检查后边缘(s.关于文件依赖关系的增强图文档)。
我现在想对是否有一些建议全部 可以通过 DFS 检测图中的循环并检查后缘？
http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf (在 S.O. 上找到)陈述了一种基于循环基础的方法。就我个人而言，我觉得它不是很直观，所以我正在寻找不同的解决方案。
编辑:我最初的意见显然是错误的。 S.“白痴”的下一个答案。
初始 观点:
我的观点是，它确实可以这样工作，因为 DFS-VISIT(DFS 的伪代码)刚刚进入尚未访问的每个节点。从这个意义上说，每个顶点都表现出一个循环的潜在开始。此外，由于 DFS 访问每条边一次，因此也涵盖了通向循环起点的每条边。因此，通过使用 DFS 和后端检查，确实应该可以检测到 全部 图中的循环。请注意，如果存在具有不同数量参与者节点的循环(例如三角形、矩形等)，则必须做额外的工作来区分每个循环的实际“形状”。
最佳答案
我已经彻底回答了这个问题，所以请检查:
Will a source-removal sort always return a maximal cycle?
答案的相关部分:
Perform a Depth-First Search on your graph.
You are interested in recognizing back edges, i.e., in the traversal, an edge which points back to an ancestor (in the DFS tree, which is induced by edges of visiting nodes for the first time) of the visited node. For example, if the DFS stack has nodes [A->B->C->D] and while you explore D you find an edge D->B, that's a back edge. Each back edge defines a cycle.
More importantly, the cycles induced by back-edges are a basic set of cycles of the graph. "A basic set of cycles": you can construct all cycles of the graph just by UNIONing and XORing cycles of the basic set. For example, consider the cycles [A1->A2->A3->A1] and [A2->B1->B2->B3->A2]. You can union them to the cycle: [A1->A2->B1->B2->B3->A2->A3->A1].
关于graph - 查找图中的所有循环，redux，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2839908/