求有向图中的所有圈

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)