Checking Presence of Cycle in Directed Graph using DFS

Here, we will be discussing an algorithm to detect the presence of the cycle in a directed graph.

Prerequisites

• Depth First Search Algorithm

Example:
Below we have two directed graphs out of which in (b) we have a path from each node to another node were as in (a) we can't move from 2 to 3.

In graph (b) we have cycles whereas in a graph (a) don't have a cycle.

Algorithm to detect the presence of a cycle.
To find the presence of a cycle we will use colouring technique. Let us say,

• Color 0: Node is not been visited ( White Node )
• Color 1: Node is currently is in processing mode ( Gray Node )
• Color 2: Node and all it's adjacent are processed. ( Black Node )

The cycle could be found when the node currently getting visited is already in processing ie. color =1. This means that we have a different path to previously visited node and hence there is cycle.

Simulation of DFS in (a):

Now let us simulate the DFS algorithm in the graph (a) starting with node 1.

• Initially, each node has Color = 0, when we start DFS(1) then it calls DFS(2) from 2 we cannot call any other node so it is processed.

• Then 1 is processed. After which we start DFS(3) which calls DFS(4). Now from 4, we can visit 2 but it is already visited, so node 4 is also processed now, and so 3 is processed.

In this, we have not got any cycle.

Simulation of DFS in (b):

Now let us simulate the DFS algorithm in the graph (b) starting with node 1.

• Let us call DFS(1) which in turn calls DFS(3) which in turn calls DFS(4) which in turn calls DFS(2) which in turn calls DFS(1) but 1 is already visited and but not yet processed so we found a cycle.

Implementation in C++

That's all for this article. If you have some content OR material related to this then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by Learn DSA