title: Detecting cycles in a graph using DFS: 2 different approaches and what's the difference
body: <p>Note that a graph is represented as an adjacency list.</p>
  
  <p>I've heard of 2 approaches to find a cycle in a graph:</p>
  
  <ol>
  <li><p>Keep an array of boolean values to keep track of whether you visited a node before. If you run out of new nodes to go to (without hitting a node you have already been), then just backtrack and try a different branch.</p></li>
  <li><p>The one from Cormen's CLRS or Skiena: For depth-first search in undirected graphs, there are two types of edges, tree and back. The graph has a cycle if and only if there exists a back edge.</p></li>
  </ol>
  
  <p>Can somebody explain what are the back edges of a graph and what's the diffirence between the above 2 methods.</p>
  
  <p>Thanks.</p>
  
  <p><strong>Update:</strong>
  Here's the code to detect cycles in both cases. Graph is a simple class that represents all graph-nodes as unique numbers for simplicity, each node has its adjacent neighboring nodes (g.getAdjacentNodes(int)):</p>
  
  <pre><code>public class Graph {
  
    private int[][] nodes; // all nodes; e.g. int[][] nodes = {{1,2,3}, {3,2,1,5,6}...};
  
    public int[] getAdjacentNodes(int v) {
      return nodes[v];
    }
  
    // number of vertices in a graph
    public int vSize() {
      return nodes.length;
    }
  
  }
  </code></pre>
  
  <p><strong>Java code to detect cycles in an undirected graph:</strong></p>
  
  <pre><code>    public class DFSCycle {
  
      private boolean marked[];
      private int s;
      private Graph g;
      private boolean hasCycle;
  
      // s - starting node
      public DFSCycle(Graph g, int s) {
          this.g = g;
          this.s = s;
          marked = new boolean[g.vSize()];
          findCycle(g,s,s);
      }
  
      public boolean hasCycle() {
          return hasCycle;
      }
  
      public void findCycle(Graph g, int v, int u) {
  
          marked[v] = true;
  
          for (int w : g.getAdjacentNodes(v)) {
              if(!marked[w]) {
                  marked[w] = true;
                  findCycle(g,w,v);
              } else if (v != u) {
                  hasCycle = true;
                  return;
              }
          }
  
      }  
  }
  </code></pre>
  
  <p><strong>Java code to detect cycles in a directed graph:</strong></p>
  
  <pre><code>public class DFSDirectedCycle {
  
      private boolean marked[];
      private boolean onStack[];
      private int s;
      private Graph g;
      private boolean hasCycle;
  
      public DFSDirectedCycle(Graph g, int s) {
          this.s = s
          this.g = g;
          marked = new boolean[g.vSize()];
          onStack = new boolean[g.vSize()];
          findCycle(g,s);
      }
  
      public boolean hasCycle() {
          return hasCycle;
      }
  
      public void findCycle(Graph g, int v) {
  
          marked[v] = true;
          onStack[v] = true;
  
          for (int w : g.adjacentNodes(v)) {
              if(!marked[w]) {
                  findCycle(g,w);
              } else if (onStack[w]) {
                  hasCycle = true;
                  return;
              }
          }
  
          onStack[v] = false;
      }
  }
  </code></pre>