在无向图的情况下，最近发表的一篇论文(无向图中循环和st路径的最优列表)提供了一个渐近最优解。你可以在这里阅读http://arxiv.org/abs/1205.2766或http://dl.acm.org/citation.cfm?id=2627951 我知道它不能回答你的问题，但由于你的问题标题没有提到方向，它可能仍然对谷歌搜索有用

深度优先搜索和回溯应该在这里工作。 保存一个布尔值数组，以跟踪您以前是否访问过某个节点。如果您没有新节点可访问(不涉及已经访问过的节点)，那么只需返回并尝试不同的分支。

如果你有一个邻接表来表示图，DFS很容易实现。例如adj[A] = {B,C}表示B和C是A的子结点。

例如，下面的伪代码。“start”是开始的节点。

dfs(adj,node,visited):  
  if (visited[node]):  
    if (node == start):  
      "found a path"  
    return;  
  visited[node]=YES;  
  for child in adj[node]:  
    dfs(adj,child,visited)
  visited[node]=NO;

用开始节点调用上面的函数:

visited = {}
dfs(adj,start,visited)

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

基于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

关于你关于排列周期的问题，请在这里阅读更多: https://www.codechef.com/problems/PCYCLE

您可以尝试以下代码(输入大小和数字number):

# include<cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);

    int num[1000];
    int visited[1000]={0};
    int vindex[2000];
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);

    int t_visited=0;
    int cycles=0;
    int start=0, index;

    while(t_visited < n)
    {
        for(int i=1;i<=n;i++)
        {
            if(visited[i]==0)
            {
                vindex[start]=i;
                visited[i]=1;
                t_visited++;
                index=start;
                break;
            }
        }
        while(true)
        {
            index++;
            vindex[index]=num[vindex[index-1]];

            if(vindex[index]==vindex[start])
                break;
            visited[vindex[index]]=1;
            t_visited++;
        }
        vindex[++index]=0;
        start=index+1;
        cycles++;
    }

    printf("%d\n",cycles,vindex[0]);

    for(int i=0;i<(n+2*cycles);i++)
    {
        if(vindex[i]==0)
            printf("\n");
        else
            printf("%d ",vindex[i]);
    }
}

CXXGraph库提供了一组检测周期的算法和函数。

要获得完整的算法解释，请访问wiki。