﻿ Finding all cycles in a directed graph using recursive backtracking

# Finding all cycles in a directed graph using recursive backtracking

I am working on finding cycles in directed graph using recursive backtracking. There is a suggested pseudocode for this here, which is here:

``````dfs(adj,node,visited):
if (visited[node]):
if (node == start):
"found a path"
return;
visited[node]=YES;
visited[node]=NO;
``````

Call the above function with the start node:

``````visited = {}
``````

While this is not the most efficient algorithm when compared to `Tarjans algorithm`, this is simple enough me for me to understand. Currently, this code does not have a count of number cycles detected.

I implemented this in 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);
Vertex next = e.target;
dfs(start,next,count);
}
v.setVisited(false);
}
``````

For the graph with following edges:
`(1 2),(2 3),(3 1),(2 5),(5 6),(6 2)`-- I get 6 cycles as output.

`(1 2),(2 3),(3 4),(4,1),(2 5),(5 6),(6 2)` -- I get 7 cycles as output.

I can see that my current code does cycle detection for each vertex that are already part of a previously detected cycle (e.g.: a cycle with three nodes gives me three cycles for each individual nodes while this must be one). I need some tips here as to what is going wrong and some fix.

For `(1 2),(2 3),(3 1)`, you're calling:

• `dfs(vertex1, vertex1, count)`, which gives you the cycle `1 -> 2 -> 3 -> 1`.
• `dfs(vertex2, vertex2, count)`, which gives you the cycle `2 -> 3 -> 1 -> 2`.
• `dfs(vertex3, vertex3, count)`, which gives you the cycle `3 -> 1 -> 2 -> 3`.

So you're counting the same cycle multiple times.

The simplest fix I can think of is simply setting the visited flag after the `dfs` call.

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