Print all the cycles in a directed graph

Question

We can use the algorithm stated here to find the number of cycles in a directed graph. I need to understand the algorithm.

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) What is the use of that last statement exactly? A short description of how the algo works would be so helpful. Since the algorithm is basically to count the num of cycles from a node back to the same node, we can use another array, call it v and do the following trick :

def dfs(adj,node,start,visited):
    if (node in v):
        return

and then write all other things intact. As part of the main function,

for i in range(len(adj)):
    dfs(adj,i,i,visited)
    v.append(i)

does the job neatly. So basically we set the visited[node] of the elements (nodes) of an already established cycle to 0 (false) forever. Not a good time complexity, but it works nonetheless.

For printing the array, my plan was to put all the elements in an array (call it A) and keep appending until a path is found. Now when the path is found, backtrack from start (now A[last_elem]) to start (which is A[some_prev_elem]). Then remove the elements from A upto the position where the recursion is supposed to continue (for example, 0->1->2->0 and 0->1->3->.. are two branches of the dfs tree, then we remove upto only the last two elements of A (which are 2 and 0) since the recursion continues from 1 now).

(2) I cannot implement the algorithm I just wrote. This is the main question but I think I need to understand (1) above to understand the code for printing all the cycles.

I understand that there are algorithms on the internet, I am trying to use this algorithm.

score 1 · Accepted Answer · answered Apr 16 '20 at 06:38

Let's try to draw a graph/tree and a call stack of DFS. In my opinion, the clue to understanding here is to keep track of how "visited" changes. For instance:

|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}
...

Here's an interesting part, please, pay attention to how 6's been changed in visited on 4th step. We just backtracked from 6th node to 2nd again and that's why 6 is not within the current path.

So, if we truly found a node in visited it means we've been going deeper and deeper without backtracking and found the node once again, which means it's a cycle.

In my example, that is what's going to happen to node 1 eventually, and you can check it if you continue to populate the table of DFS calls.

That makes sense. How do we print all the paths now? It still doesn't seem direct to me. Backtracking to find paths isn't still clear to me. — oldsailorpopoye, Apr 20 '20 at 01:34
If you take visited and print all the keys which correspond to "yes" values — that is the path. You may do it when a cycle detected. — vitkarpov, Apr 21 '20 at 12:47

Print all the cycles in a directed graph

1 Answers1