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

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

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.

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

I think the above code works only for a connected digraph since we start dfs from the source node only, for if the digraph is not connected there may be a cycle in the other component which may go unnoticed!

Here is the code I've written in C based on DFS to find out whether a given undirected graph is connected/cyclic or not. with some sample output at the end. Hope it'll be helpful :)

#include<stdio.h>
#include<stdlib.h>

/****Global Variables****/
int A[20][20],visited[20],count=0,n;
int seq[20],connected=1,acyclic=1;

/****DFS Function Declaration****/
void DFS();

/****DFSearch Function Declaration****/
void DFSearch(int cur);
	
/****Main Function****/
int main() 
   {	
	int i,j;

	printf("\nEnter no of Vertices: ");
 	scanf("%d",&n);

	printf("\nEnter the Adjacency Matrix(1/0):\n");
 	for(i=1;i<=n;i++)
    	    for(j=1;j<=n;j++)
		scanf("%d",&A[i][j]);
	
	printf("\nThe Depth First Search Traversal:\n");

	DFS();

	for(i=1;i<=n;i++)
	    printf("%c,%d\t",'a'+seq[i]-1,i);

	if(connected && acyclic)    printf("\n\nIt is a Connected, Acyclic Graph!");
	if(!connected && acyclic)   printf("\n\nIt is a Not-Connected, Acyclic Graph!");
	if(connected && !acyclic)   printf("\n\nGraph is a Connected, Cyclic Graph!");
	if(!connected && !acyclic)  printf("\n\nIt is a Not-Connected, Cyclic Graph!");
		
	printf("\n\n");
	return 0;
   }

/****DFS Function Definition****/
void DFS()
    { 
	int i;
	for(i=1;i<=n;i++)
	    if(!visited[i])
	      {
		if(i>1) connected=0;
		DFSearch(i);	
              } 
    }

/****DFSearch Function Definition****/
void DFSearch(int cur) 
    {
	int i,j;
	visited[cur]=++count;

    	seq[count]=cur; 
      	for(i=1;i<count-1;i++)
                if(A[cur][seq[i]]) 
           	       acyclic=0;

   	for(i=1;i<=n;i++)
  	    if(A[cur][i] && !visited[i])
	       DFSearch(i);
	
    }

	

Sample Output:

majid@majid-K53SC:~/Desktop$ gcc BFS.c

majid@majid-K53SC:~/Desktop$ ./a.out
************************************
	 
Enter no of Vertices: 10

Enter the Adjacency Matrix(1/0):

0 0 1 1 1 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 1 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 1 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 0 1 
0 0 0 0 0 0 1 0 0 0 

The Depdth First Search Traversal:
a,1	c,2	d,3	f,4	b,5	e,6	g,7	h,8	i,9	j,10	

It is a Not-Connected, Cyclic Graph!


majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 4

Enter the Adjacency Matrix(1/0):
0 0 1 1
0 0 1 0
1 1 0 0
0 0 0 1

The Depth First Search Traversal:
a,1	c,2	b,3	d,4	

It is a Connected, Acyclic Graph!


majid@majid-K53SC:~/Desktop$ ./a.out
************************************

Enter no of Vertices: 5

Enter the Adjacency Matrix(1/0):
0 0 0 1 0
0 0 0 1 0
0 0 0 0 1
1 1 0 0 0 
0 0 1 0 0

The Depth First Search Traversal:
a,1	d,2	b,3	c,4	e,5	

It is a Not-Connected, Acyclic Graph!

*/