Detect cycles in a graph using DFS

Introduction

In this post I'm going to talk how to detect if there is a cycle in a graph. Which means can there be more than one way of reaching any node from any other node in the graph. This is completely implemented using the DFS which I have already talked about in a previous blog post. So this will be short blog with only the basics.

In DFS we are using a stack data structure. At the same time we keep track of visited nodes to be ignored in case we find them later in the algorithms. This ignorance is the key point in detecting a cycle. DFS yields a tree out of the graph. Thus there cannot be cycles. Hence we ignore repeated nodes when we go deep through the neighbouring nodes of a graph.

Algorithm and Implementation 

 

Let us consider the above directed graph. Starting from A in a typical DFS we move through nodes as follows.

A->B->C->E->F

since F is a terminal node we have again E at the node.

A->B->C->E

Now the stack becomes something like this

A->B->C->D (Pop out E and put D) and continuing

A->B->C->B

A->B->C->C

now we pop out C (Remember we shall mark what we pop as visited)

now we have 

A->B->C

Bingo, we again pop out C which has already been discovered. Here we conclude that there is a cycle. What really means here is that we have a path to C from A B C E and we again reach C which makes the cycle. This is simple and operates in O(n) time, where n is the number of nodes.

Java implementation is as follows:

Feel free to visit the original repository of algorithms at:
URL https://github.com/anuradhawick/Algorithms