我正在使用递归回溯在有向图中寻找循环。这里有一个建议的伪代码,这里是:
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;
使用起始节点调用上述函数:
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 个周期作为输出。
我可以看到我当前的代码对已经是先前检测到的循环的一部分的每个顶点进行循环检测(例如:具有三个节点的循环为每个单独的节点提供了三个循环,而这必须是一个)。我需要一些提示,说明出了什么问题并进行了一些修复。