我如何才能找到(遍历)有向图中从/到给定节点的所有周期?
例如，我想要这样的东西:
A->B->A
A->B->C->A
而不是: B - > C > B
当前回答
CXXGraph库提供了一组检测周期的算法和函数。
要获得完整的算法解释，请访问wiki。
其他回答
深度优先搜索和回溯应该在这里工作。 保存一个布尔值数组，以跟踪您以前是否访问过某个节点。如果您没有新节点可访问(不涉及已经访问过的节点)，那么只需返回并尝试不同的分支。
如果你有一个邻接表来表示图，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
从节点X开始，检查所有子节点(如果无方向，父节点和子节点是等价的)。将这些子节点标记为X的子节点。对于任何这样的子节点A，标记它的子节点是A的子节点，X'，其中X'标记为2步远。)如果您稍后点击X并将其标记为X的子节点”，这意味着X处于3节点周期中。回溯到它的父节点很容易(因为算法不支持这一点，所以你可以找到任何一个有X'的父节点)。
注意:如果图是无向的或者有任何双向边，这个算法会变得更复杂，假设你不想在一个周期内两次遍历同一条边。
CXXGraph库提供了一组检测周期的算法和函数。
要获得完整的算法解释，请访问wiki。
我无意中发现了下面的算法，它似乎比Johnson的算法更有效(至少对于更大的图)。然而，与Tarjan的算法相比，我不确定它的性能如何。 此外，到目前为止，我只检查了三角形。如果感兴趣，请参阅千叶Norishige和西泽木高雄(http://dx.doi.org/10.1137/0214017)的“树状性和子图列表算法”
