Detecting cycles in a graph using DFS: 2 different approaches and what's the difference

Question

Note that a graph is represented as an adjacency list.

I've heard of 2 approaches to find a cycle in a graph:

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

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

Can somebody explain what are the back edges of a graph and what's the diffirence between the above 2 methods.

Thanks.

Update: 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)):

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

Java code to detect cycles in an undirected graph:

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

Java code to detect cycles in a directed graph:

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

Answer 1

Answering my question:

The graph has a cycle if and only if there exists a back edge. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS forming a cycle.

Both approaches above actually mean the same. However, this method can be applied only to undirected graphs.

The reason why this algorithm doesn't work for directed graphs is that in a directed graph 2 different paths to the same vertex don't make a cycle. For example: A-->B, B-->C, A-->C - don't make a cycle whereas in undirected ones: A--B, B--C, C--A does.

Find a cycle in undirected graphs

An undirected graph has a cycle if and only if a depth-first search (DFS) finds an edge that points to an already-visited vertex (a back edge).

Find a cycle in directed graphs

In addition to visited vertices we need to keep track of vertices currently in recursion stack of function for DFS traversal. If we reach a vertex that is already in the recursion stack, then there is a cycle in the tree.

Update: Working code is in the question section above.

Answer 2

For the sake of completion, it is possible to find cycles in a directed graph using DFS (from wikipedia):

 L ← Empty list that will contain the sorted nodes while there are unmarked nodes do     select an unmarked node n     visit(n)  function visit(node n)     if n has a temporary mark then stop (not a DAG)     if n is not marked (i.e. has not been visited yet) then         mark n temporarily         for each node m with an edge from n to m do             visit(m)         mark n permanently         unmark n temporarily         add n to head of L