Is backtracking absolutely necessary for cycle detection using DFS in directed graph?

Question

I came across this SO post where it is suggested that cycle detection using DFS in a directed graph is faster because of backtracking. Here I quote from that link:

Depth first search is more memory efficient than breadth first search as you can backtrack sooner. It is also easier to implement if you use the call stack but this relies on the longest path not overflowing the stack.

Also if your graph is directed then you have to not just remember if you have visited a node or not, but also how you got there. Otherwise you might think you have found a cycle but in reality all you have is two separate paths A->B but that doesn't mean there is a path B->A. With a depth first search you can mark nodes as visited as you descend and unmark them as you backtrack.

Why is backtracking essential?

Can someone explain with an example graph as what is meant in the given A->B example?

Finally, I have a DFS code for cycle detection in directed graph that does not use backtracking but still detects cycle in O(E+V).

public boolean isCyclicDirected(Vertex v){
  if (v.isVisited) {
    return true;
  }
  v.setVisited(true);
  Iterator<Edge> e = v.adj.iterator();
  while (e.hasNext()) {
    Vertex t = e.next().target;
    // quick test:
    if (t.isVisited) {
      return true;
    }
    // elaborate, recursive test:
    if (isCyclicDirected(t)) {
      return true;
    }
  }
  // none of our adjacent vertices flag as cyclic
  v.setVisited(false);
  return false;
}

Mackintosh

if (t.isVisited) { return true; } is uneccessary because when isCyclicDirected(t) is called the first thing it will do is check if the Vertex passed in has been visited. – Lost

@Floegipoky: agreed! very valid point! but the algorithm is correct overall right? – Mackintosh

No, unfortunately it is not correct. However, if you added v.setVisited(false); right before the return false; I think it would be! :) – Lost

@Floegipoky: yes, I just figured it out. Thanks for it, I am editing the post – Mackintosh

In general you should refrain from fixing code in the question as this tends to invalidate some (parts of or entire) answers. In this case it's probably minor enough. – Cordwood

@Dukeling: I will follow this from now on – Mackintosh

Answer 1

Why you need to backtrack:

A -> B
^ \
|  v
D <- C

If you go A -> B and you don't backtrack, you'll stop there and you won't find the cycle.

Your algorithm does backtrack. You're just wrapping it in recursion so it might not quite look the way you expect. You recurse for one of the neighbours, if this doesn't find a cycle, that call returns and you try some other neighbour - this is backtracking.

Why you need to remember how you got to where you are:

A -> B
  \  ^
   v |
     C

The above graph has no cycle, but if you go A -> B, then A -> C -> B, you'll think there is if you don't remember the path.

As mentioned in the linked post, you can just set the visited flag to false before returning in your code (which I see you've now done) - this will act as remembering the path.

Cordwood

1. when I backtrack, I should setVisited flag to be false, before I do the next iteration, I quote from above With a depth first search you can mark nodes as visited as you descend and unmark them as you backtrack., but I do not unset the flag visited. so why do you say I backtrack – Mackintosh

It will not stop there (A->B). looking at my code this works because I iterate over all the adjacent nodes of A, i.e after I go through A->B, I come back and do A->C and any other adjacent nodes..so I think backtracking is not essential – Mackintosh

Sorry, I'm just confusing myself now. You do backtrack because that's what recursion does - you recurse for one of the neighbours, if this doesn't find a cycle, that call returns and you try some other neighbour - this is backtracking. True, it won't stop at A -> B, but your code will return true for some graphs that don't have cycles, as per the second part of my answer. – Cordwood

yes, it failed for the example graph you provided, but I fixed with turning the visited flag off and now it works fine. since I am doing setVisited(false) , I am doing backtrack, I remember the backtrack pattern as set, recurse, unset – Mackintosh

on a similar note, I see a dfs with backtracking solution was provided to find all cycles in a graph here: https://mcmap.net/q/36817/-finding-all-cycles-in-a-directed-graph third answer, but I do not see how it find all the cycles, I left the comment there. but got no reply – Mackintosh

Answer 2

It's worth pointing out that this marking algorithm is an adaptation of the naive approach to linked list cycle detection that involves keeping track of each node visited so far. In this case the path followed by the recursion is treated as a linked list and the linked list algorithm is applied. The space complexity is what makes the algorithm sub-optimal for linked lists, since you need to hold a reference to each node in the list it is O(n). When you're applying this to a decently well-balanced graph howeever, the space complexity drops to O(logn). In the case where the graph is a tree, the space complexity degrades to O(n) but you get O(n) time complexity.

Also, the algorithm is still incorrect. Given a graph with nodes A and B and a single edge B->B, isCyclicDirected(A) will never detect the cycle.

Lost

Note that the algorithm is incorrect for the reason you mentioned if the function is only called for one vertex (it won't work for a different reason if it's called for each vertex, but then all visited flags also have to be reset after each call, which would make the running time more than mentioned). – Cordwood

I think that the edited version will return the correct answer if it's called for each vertex, but as you say the runtime will be unacceptable – Lost

You should be able to improve the running time by having another visited array for vertices visited in the primary call, which you don't ever visit again. This should significantly cut down on the running time, but I believe it would still be exponential in the worst case. – Cordwood

@Dukeling: The version I provided already has the best running time for a connected graph correct? why having another visited array of vertices is helpful? I am marking an array that is already visited through its field.. – Mackintosh

@Floegipoky: please see my above comment for Dukeling – Mackintosh

@user1988876 As I said in the answer, the algorithm as posted is not yet correct because it will not detect cycles in every case (like the case I specify). There is a fix involving an additional list. – Lost

Answer 3

backtracking is not essential only if your graph doesn't have any case where you can get from node A to node B by two different paths. Your algo will detect a false positive in the case mentioned in the previous answer: A -> B \ ^ v | C But if you add backtracking your alto will work perfectly, even in the case above.

Leptosome