在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

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

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

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

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

我曾经在面试中遇到过这样的问题，我怀疑你遇到过这种情况，你来这里寻求帮助。把这个问题分解成三个问题就容易多了。

如何确定下一个有效点 路线 你如何确定一个点是否存在 被使用 你如何避免越过 同样的观点

问题1) 使用迭代器模式提供迭代路由结果的方法。放置获取下一个路由的逻辑的一个好地方可能是迭代器的“moveNext”。要找到有效的路由，这取决于您的数据结构。对我来说，这是一个sql表充满有效的路由可能性，所以我必须建立一个查询，以获得有效的目的地给定的源。

问题2) 当您找到每个节点时，将它们推入一个集合，这意味着您可以通过动态询问正在构建的集合，很容易地查看是否在某个点上“返回”。

问题3) 如果在任何时候你看到你正在折回，你可以从集合中弹出东西并“后退”。然后从这一点开始，再次尝试“前进”。

黑客:如果你正在使用Sql Server 2008，有一些新的“层次结构”的东西，你可以用它来快速解决这个问题，如果你把你的数据结构成树状。

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

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