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.

Answer 1

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.