使用递归回溯在有向图中查找所有周期

我正在使用递归回溯来查找有向图中的循环。 这里有一个建议的伪代码， 在这里：

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) 

虽然与Tarjans algorithm相比，这不是最有效的算法，但这对我来说很容易理解。 目前，此代码没有检测到的数字周期数。

我用Java实现了这个：

 //this is the main method that calls the helper DFS which runs on each node public int allCyclesDirectedmain(){ //this initializes all vertices clearAll(); int[] count = new int[1]; for (Vertex v: vertexMap.values()){ //System.out.println(v.name); //clearAll(); dfs(v,v,count); } return count[0]; } //start and v are same when the method first fires. public void dfs(Vertex start, Vertex v,int[] count){ if (v.isVisited){ if (start==v){ //found a path count[0]++; } return ; } v.setVisited(true); for (Edge e : v.adj){ Vertex next = e.target; dfs(start,next,count); } v.setVisited(false); } 

对于具有以下边缘的图形：
(1 2),(2 3),(3 1),(2 5),(5 6),(6 2) – 我得到6个循环作为输出。

(1 2),(2 3),(3 4),(4,1),(2 5),(5 6),(6 2) – 我得到7个循环作为输出。

我可以看到我的当前代码对已经是先前检测到的周期的一部分的每个顶点进行周期检测（例如：具有三个节点的周期为每个单独的节点提供三个周期，而这必须是一个）。 我需要一些关于出了什么问题和一些修复的提示。

Answer 1

对于(1 2),(2 3),(3 1) ，您正在呼叫：

• dfs(vertex1, vertex1, count) ，它给你循环1 -> 2 -> 3 -> 1 。
• dfs(vertex2, vertex2, count) ，它给你循环2 -> 3 -> 1 -> 2 。
• dfs(vertex3, vertex3, count) ，它给你循环3 -> 1 -> 2 -> 3 。

所以你要多次计算同一个周期。

我能想到的最简单的解决方法就是在dfs调用之后设置被访问标志。

 public int allCyclesDirectedmain(){ clearAll(); int[] count = new int[1]; for (Vertex v: vertexMap.values()){ dfs(v,v,count); v.setVisited(true); // <--- } return count[0]; }