求有向图中的所有圈

Question

求有向图中的所有圈

如何找到(迭代)一个有向图中从/到给定节点的所有循环？

例如，我想要这样的东西：

A->B->A
A->B->C->A

但不是：B->C->B

Answer 1

深度优先搜索与回溯应该在这里工作。保持布尔值数组，以跟踪之前是否访问过节点。如果您没有足够的新节点去访问(而没有触及您已经访问过的节点)，那么只需回溯并尝试另一个分支。如果您有一个表示图的邻接列表，则DFS很容易实现。例如，adj[A]={B，C}表示B和C是A的子级。例如，下面的伪代码。“开始”是从哪个节点开始的。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;使用Start节点调用上面的函数：visited = {} dfs(adj,start,visited)