在有向图中打印所有循环

Question

我们可以使用表示为here的算法来查找有向图中的循环数。我需要了解算法。

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）最后一条语句的确切用途是什么？简短描述算法的工作原理将非常有帮助。由于该算法基本上是计算从一个节点返回到同一节点的循环数，因此我们可以使用另一个数组，将其称为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)

做好工作。因此，基本上，我们将已经建立的循环的元素（节点）的visited [node]永远设置为0（false）。时间复杂度不高，但是仍然可以。

对于打印数组，我的计划是将所有元素放入数组（称为A），并一直追加直到找到路径。现在，找到路径后，从起点（现在为A [last_elem]）回溯到起点（即A [some_prev_elem]）。然后从A移除元素，直到递归应该继续的位置（例如0-> 1-> 2-> 0和0-> 1-> 3-> ..是dfs树的两个分支，然后，由于递归从1开始继续进行，因此我们仅删除A的最后两个元素（分别是2和0）。

（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}
...

[这是一个有趣的部分，请注意在第四步访问时6的变化。我们再次从第6个节点backtracked到第2个节点，这就是为什么6不在当前路径内的原因。

因此，如果我们确实在访问中找到一个节点，则意味着我们一直在深入研究而没有回溯，并再次找到该节点，这意味着它是一个循环。

在我的示例中，这最终将在节点1上发生，如果继续填充DFS调用表，则可以检查它。