Detect Cycle in a Directed Graph

We are given a directed graph with V vertices and we have to find whether this directed graph contains a cycle or not. A cycle in a graph is a non-empty trail in which the first and last vertices are repeated. A graph continuing at least one cycle is also known as a cyclic graph. Note the graph can contain self-loop too.

Example –
Consider the following two directed graphs. The graph1 contains a cycle (2->4->5->2) colored red while the graph2 doesn’t contain any cycle.

DFS based solution

The Depth First Search(DFS) is used to find a cycle in the graph. Since this is a directed graph, if we use DFS directly it will result in incorrect results hence we will modify the DFS as explained below to find the cycle in the directed graph.

In a directed graph, a cycle will exist only if there exists a back edge. A back edge is an edge that is from a node to itself (self-loop) or one of its ancestors in the tree produced by DFS Hence while performing the DFS traversal we have to check for the back edge as it will lead to a cycle.

Hence instead of using a single stack, we will modify DFS to use two stacks i.e. visited & re_visisted stacks. The first time we will encounter an element we will push it to the visited stack and once we have visited all the neighbors of the current element, then we will move it to the revised stack.

The cycle will exist if the current element is in the visited stack and the neighbor of the current node(or its adjacent node) is visited stack too, this means there exists a cycle (as it means there exists a back edge which leads to starting node of the DFS tree).

Let’s understand the working of the above algorithm by applying it on Graph 1.

Consider the above Graph 1 and dry run the
above algorithm on it.
Let's start from Node 1.
Intitally -> visited = {} & re_visited = {}

1. DFS(1) - visited = {1} & re_visited = {}
            Neighbours of 1 -> NULL
            visited = {} & re_visited = {1}
            return 

2. DFS(2) - visited = {2} & re_visited = {1}
            Neighbours of 2 -> {1, 3, 4, 5}
            Call DFS on each neighbours of 2.
   
   DFS(1) - visited = {2} & re_visited = {1}
            re_visited contains 1, 
            return

   DFS(3) - visited = {2, 3} & re_visited = {1}
            Neighbours of 3 -> {1}
            1 is already in revisited stack.
            visited = {2} & re_visited = {1, 3}
            return

   DFS(4) - visited = {2, 4} & re_visited = {1, 3}
            Neighbours of 4 -> {5}
            Call DFS on each neighbour of 4

   DFS(5) - visited = {2, 4, 5} & re_visited = {1, 3}
            Neighbours of 5 -> {2}
            Call DFS on each neighbour of 5
  
   DFS(2) - visited = {2, 4, 5} & re_visited = {1, 3}
            since 2 is already in a visited stack.
            This means there is a cycle.
            Hence return True(cycle exits).

Algorithm

1. Create a graph using the Adjacency List and call isCyclic() function.
2. Create two empty stack i.e. visited[] & and re_visited[]
3. For each node of the graph, if it is not in the re_visited stack call the DFS function for it.
4. For each node passed as a parameter in DFS function
   1. If the element is in the visited[] stack, return true(cycle exists).
   2. If not move the function to visited[] stack.
   3. Call the DFS function for each neighbor of the current node.
   4. Finally, move the node from the visited[] stack to the re_visited[] stack.

Implementation of the above Algorithm

// C++ Program to detect cycle 
// in a directed graph

#include <bits/stdc++.h>
using namespace std;

//DFS fucntion to visit all nodes  
//adjacent to the current node
bool dfs(int i, vector<int>adj[], bool* visited, bool* re_visited)
{
    //if the vertex is already in a visited
    //stack, then there is a cycle hence
    //return true, which means, cycles exists. 
    if(visited[i] == true)
        return true;

    //add current vetex to visted stack
    visited[i] = true;

    //variable to store the final result
    bool res = false;
    
    //for all the directed edges originating
    //from the current vertex
    for(int j=0; j<adj[i].size(); j++)
    {    
        //If current vertex is not
        //in the re_visited stack yet.
        if(re_visited[adj[i][j]] == false)
        {
            //update the final result with the result returned
            //by all the adjacent nodes. This will be true, if 
            //any adjacent nodes returns true(cycle exits)
            res = res || dfs(adj[i][j], adj, visited, re_visited);
        }
    }
    
    //remove the current vertex from the 
    //visited stack and insert it into
    //the re_visited stack
    visited[i] = false;
    re_visited[i] = true;

    return res;
}

//Function to return if the directed graph
//contians cycle or not
bool isCyclic(int v, vector<int> adj[])
{
    //intitialize visited and re_visited stack
    bool visited[v+1], re_visited[v+1];

    bool res = false;
    
    //set visited and re_visited stack to false
    for(int i=0; i<v; i++){
       visited[i] = false;
       re_visited[i] = false;
    }
    
    //for every vertex which is not in
    //re_visited stack, call dfs for it
    for(int i=0; i<v; i++)
    {
        //If current vertex isn't visited yet.
        if(re_visited[i] == false)
            res = res || dfs(i, adj, visited, re_visited);
    }

    return res;
}

//Driver Program 
int main() {
    
    int v = 8, e = 6;
        
    vector<int> adj[v];
        
    adj[2].push_back(3);
    adj[2].push_back(7);
    adj[2].push_back(4);
    adj[3].push_back(7);
    adj[4].push_back(5);
    adj[5].push_back(2);

    //if isCyclic function returns true
    if(isCyclic(v, adj) == true)
        cout<<"Graph contains cycle"<< endl;
    //if isCyclic function returns false 
    else
        cout<<"Graph doesn't contain cycle"<< endl;
        
    
    return 0;
} 

Output
Graph contains cycle

Time Complexity

The Time Complexity of this algorithm is O(V+E). The Time Complexity of this method is the same as the time complexity of DFS traversal which is O(V+E).
The Space Complexity is O(V) that is needed to store the visited and re_visited stack of size V(number of vertices)