title: Is backtracking absolutely necessary for cycle detection using DFS in directed graph?
body: <p>I came across this <a href="https://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs">SO post</a> where it is suggested that cycle detection using DFS in a directed graph is faster because of backtracking. Here I quote from that link:</p>
  
  <blockquote>
    <p>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.</p>
    
    <p>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.</p>
  </blockquote>
  
  <p>Why is backtracking essential?</p>
  
  <p>Can someone explain with an example graph as what is meant in the given <code>A-&gt;B</code> example?</p>
  
  <p>Finally, I have a <code>DFS</code> code for cycle detection in directed graph that does not use backtracking but still detects cycle in <code>O(E+V)</code>. </p>
  
  <pre class="lang-java prettyprint-override"><code>public boolean isCyclicDirected(Vertex v){
    if (v.isVisited) {
      return true;
    }
    v.setVisited(true);
    Iterator&lt;Edge&gt; 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;
  }
  </code></pre>