打印有向图中的所有循环

Question

我们可以用这里所述的算法求有向图中的圈数。我需要理解算法。

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; #<- why?

（1）最后那句话到底有什么用处？对algo的工作原理进行简短的描述会很有帮助。由于算法基本上是统计从一个节点返回到同一节点的周期数，所以我们可以使用另一个数组，称之为v，并做以下技巧：

def dfs(adj,node,start,visited):
    if (node in v):
        return

for i in range(len(adj)):
    dfs(adj,i,i,visited)
    v.append(i)

（2）我不能实现我刚才写的算法。这是主要的问题，但我认为我需要理解上面的（1）来理解打印所有循环的代码。

我了解到互联网上有算法，我正在尝试使用这个算法。

Answer 1

让我们尝试绘制一个图/树和DFS的调用堆栈。在我看来，理解这里的线索是要跟踪“被访问的”是如何变化的。例如：

|step |node |visited
|1    |1    |{1: yes}     
|2    |2    |{1: yes, 2: yes}
|3    |6    |{1: yes, 2: yes, 6: yes}
|4    |7    |{1: yes, 2: yes, 6: no, 7: yes}
...

这里有一个有趣的部分，请注意第4步访问的6是如何改变的。我们刚刚从第6个节点返回到第2个节点，这就是为什么第6个节点不在当前路径中的原因。

所以，如果我们真的在visited中找到了一个节点，那意味着我们一直在不断地深入，没有回溯，并且再次找到了这个节点，这意味着这是一个循环。

在我的示例中，这就是节点1最终会发生的情况，如果继续填充DFS调用表，您可以检查它。