Finding all cycles in a directed graph using recursive backtracking

Question

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;  
  for child in adj[node]:  
    dfs(adj,child,visited)
  visited[node]=NO;

Call the above function with the start node:

visited = {}
dfs(adj,start,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);
   for (Edge e : v.adj){
       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.

Can you upload all your code here? I want to try it in python and would be helpful if you upload it — Lee Yaan
– Lee Yaan, Commented Jan 9, 2018 at 19:09
can you please upload the whole code, i want to implement it on my side. Please — Vishwa Ratna
– Vishwa Ratna, Commented Aug 12, 2019 at 9:56

Bernhard Barker · Accepted Answer · 2013-12-13 22:37:02Z

4

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];
}

edited Dec 13, 2013 at 22:37

answered Dec 13, 2013 at 22:14

Bernhard Barker

55.7k14 gold badges111 silver badges143 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

brain storm Over a year ago

what is the run time analysis here? I think it must be (V+E)^2, correct?

Bernhard Barker Over a year ago

I'm not 100% sure, but I think it's O(V^b), where b is the average branching factor (number of outgoing edges), or perhaps closer to O(P(V,b)) (P indicating permutations).

Vishwa Ratna Over a year ago

@Dukeling , can you please upload the whole code, i want to implement it on my side. Please.

Bernhard Barker Over a year ago

@ExceptionHandler I don't think I ever had more code than I posted here.

Collectives™ on Stack Overflow

Finding all cycles in a directed graph using recursive backtracking

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related