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

如果你有一个邻接表来表示图，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)

我在搜索中找到了这个页面，由于循环与强连接组件不相同，我继续搜索，最后，我找到了一个高效的算法，它列出了有向图的所有(基本)循环。这篇论文来自唐纳德·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的算法是最快的。

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

我无意中发现了下面的算法，它似乎比Johnson的算法更有效(至少对于更大的图)。然而，与Tarjan的算法相比，我不确定它的性能如何。 此外，到目前为止，我只检查了三角形。如果感兴趣，请参阅千叶Norishige和西泽木高雄(http://dx.doi.org/10.1137/0214017)的“树状性和子图列表算法”

在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

关于你关于排列周期的问题，请在这里阅读更多: 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]);
    }
}