打印有向图中的所有循环

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（假）。时间复杂度不是很好，但它仍然有效。

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

(2) 我无法实现我刚刚编写的算法。这是主要问题，但我想我需要理解上面的 (1) 才能理解打印所有循环的代码。

我知道网上有算法，我正在尝试使用这个算法。

Answer 1

我们试着画一个graph/tree和DFS的调用栈。在我看来，理解这里的线索是跟踪 "visited" 是如何变化的。例如：

|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 不在 当前路径 .

内的原因

所以，如果我们真的找到了一个访问过的节点，说明我们一直在越走越深，没有回溯，再次找到了这个节点，这就是一个循环。

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

打印有向图中的所有循环

Print all the cycles in a directed graph

algorithm

graph

directed-graph

cycle