基于dfs的带有后边缘的变体确实会发现循环，但在许多情况下，它不会是最小循环。一般来说，DFS给出了存在循环的标志，但它不足以真正找到循环。例如，想象5个不同的循环共用两条边。仅仅使用DFS(包括回溯变量)没有简单的方法来识别周期。

Johnson算法确实给出了所有唯一的简单循环，并具有良好的时间和空间复杂度。

但如果你只想找到最小循环(意味着可能有多个循环通过任何顶点，我们感兴趣的是找到最小循环)，并且你的图不是很大，你可以尝试使用下面的简单方法。 它非常简单，但与约翰逊的相比相当慢。

So, one of the absolutely easiest way to find MINIMAL cycles is to use Floyd's algorithm to find minimal paths between all the vertices using adjacency matrix. This algorithm is nowhere near as optimal as Johnson's, but it is so simple and its inner loop is so tight that for smaller graphs (<=50-100 nodes) it absolutely makes sense to use it. Time complexity is O(n^3), space complexity O(n^2) if you use parent tracking and O(1) if you don't. First of all let's find the answer to the question if there is a cycle. The algorithm is dead-simple. Below is snippet in Scala.

  val NO_EDGE = Integer.MAX_VALUE / 2

  def shortestPath(weights: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        weights(i)(j) = throughK
      }
    }
  }

Originally this algorithm operates on weighted-edge graph to find all shortest paths between all pairs of nodes (hence the weights argument). For it to work correctly you need to provide 1 if there is a directed edge between the nodes or NO_EDGE otherwise. After algorithm executes, you can check the main diagonal, if there are values less then NO_EDGE than this node participates in a cycle of length equal to the value. Every other node of the same cycle will have the same value (on the main diagonal).

为了重建周期本身，我们需要使用带有父跟踪的稍微修改版本的算法。

  def shortestPath(weights: Array[Array[Int]], parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = k
        weights(i)(j) = throughK
      }
    }
  }

如果顶点之间有边，父矩阵最初应该包含边缘单元中的源顶点索引，否则为-1。 函数返回后，对于每条边，您都将引用到最短路径树中的父节点。 然后很容易恢复实际的循环。

总之，我们有下面的程序来求所有的最小循环

  val NO_EDGE = Integer.MAX_VALUE / 2;

  def shortestPathWithParentTracking(
         weights: Array[Array[Int]],
         parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = parents(i)(k)
        weights(i)(j) = throughK
      }
    }
  }

  def recoverCycles(
         cycleNodes: Seq[Int], 
         parents: Array[Array[Int]]): Set[Seq[Int]] = {
    val res = new mutable.HashSet[Seq[Int]]()
    for (node <- cycleNodes) {
      var cycle = new mutable.ArrayBuffer[Int]()
      cycle += node
      var other = parents(node)(node)
      do {
        cycle += other
        other = parents(other)(node)
      } while(other != node)
      res += cycle.sorted
    }
    res.toSet
  }

还有一个小的main方法来测试结果

  def main(args: Array[String]): Unit = {
    val n = 3
    val weights = Array(Array(NO_EDGE, 1, NO_EDGE), Array(NO_EDGE, NO_EDGE, 1), Array(1, NO_EDGE, NO_EDGE))
    val parents = Array(Array(-1, 1, -1), Array(-1, -1, 2), Array(0, -1, -1))
    shortestPathWithParentTracking(weights, parents)
    val cycleNodes = parents.indices.filter(i => parents(i)(i) < NO_EDGE)
    val cycles: Set[Seq[Int]] = recoverCycles(cycleNodes, parents)
    println("The following minimal cycle found:")
    cycles.foreach(c => println(c.mkString))
    println(s"Total: ${cycles.size} cycle found")
  }

输出是

The following minimal cycle found:
012
Total: 1 cycle found

http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf

澄清:

Strongly Connected Components will find all subgraphs that have at least one cycle in them, not all possible cycles in the graph. e.g. if you take all strongly connected components and collapse/group/merge each one of them into one node (i.e. a node per component), you'll get a tree with no cycles (a DAG actually). Each component (which is basically a subgraph with at least one cycle in it) can contain many more possible cycles internally, so SCC will NOT find all possible cycles, it will find all possible groups that have at least one cycle, and if you group them, then the graph will not have cycles. to find all simple cycles in a graph, as others mentioned, Johnson's algorithm is a candidate.

我在搜索中找到了这个页面，由于循环与强连接组件不相同，我继续搜索，最后，我找到了一个高效的算法，它列出了有向图的所有(基本)循环。这篇论文来自唐纳德·b·约翰逊(Donald B. Johnson)，可以在以下链接中找到:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

java实现可以在下面找到:

http://normalisiert.de/code/java/elementaryCycles.zip

约翰逊算法的Mathematica演示可以在这里找到，实现可以从右边下载(“下载作者代码”)。

注:实际上，这个问题有很多算法。本文列举了其中一些:

http://dx.doi.org/10.1137/0205007

根据文章，Johnson的算法是最快的。

在DAG中查找所有循环涉及两个步骤(算法)。

第一步是使用Tarjan的算法找到强连接组件的集合。

从任意顶点开始。 这个顶点的DFS。每个节点x保留两个数字，dfs_index[x]和dfs_lowval[x]。 Dfs_index [x]存储访问节点的时间，而dfs_lowval[x] = min(dfs_low[k]) where K是x的所有子结点在dfs生成树中不是x的父结点。 具有相同dfs_lowval[x]的所有节点都在同一个强连接组件中。

第二步是在连接的组件中找到循环(路径)。我的建议是使用改进版的Hierholzer算法。

这个想法是:

Choose any starting vertex v, and follow a trail of edges from that vertex until you return to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph. As long as there exists a vertex v that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from v, following unused edges until you return to v, and join the tour formed in this way to the previous tour.

下面是带有测试用例的Java实现的链接:

http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html

首先，你并不是真的想要找出所有的循环因为如果有1个，那么就会有无穷多个循环。比如A-B-A, A-B-A- b - a等等。或者可以将2个循环组合成一个8-like循环等等……有意义的方法是寻找所有所谓的简单循环——那些除了开始/结束点之外不交叉的循环。如果你愿意，你可以生成简单循环的组合。

One of the baseline algorithms for finding all simple cycles in a directed graph is this: Do a depth-first traversal of all simple paths (those that do not cross themselves) in the graph. Every time when the current node has a successor on the stack a simple cycle is discovered. It consists of the elements on the stack starting with the identified successor and ending with the top of the stack. Depth first traversal of all simple paths is similar to depth first search but you do not mark/record visited nodes other than those currently on the stack as stop points.

The brute force algorithm above is terribly inefficient and in addition to that generates multiple copies of the cycles. It is however the starting point of multiple practical algorithms which apply various enhancements in order to improve performance and avoid cycle duplication. I was surprised to find out some time ago that these algorithms are not readily available in textbooks and on the web. So I did some research and implemented 4 such algorithms and 1 algorithm for cycles in undirected graphs in an open source Java library here : http://code.google.com/p/niographs/ .

顺便说一句，因为我提到了无向图:它们的算法是不同的。构建一棵生成树，然后每一条不属于树的边与树中的一些边一起形成一个简单的循环。这样发现的循环形成了所谓的循环基。所有的简单循环都可以通过组合两个或多个不同的基循环来找到。更多细节请参见:http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf。