Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Medium

Detect Cycles in a Directed Graph

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Graphs are one of the topics in Data Structures where people tend to struggle more however is not all that complicated once you grasp the basic concepts. Here we are going to discuss one of the most basic concepts that are utilized numerous times, not only just in graphs but at many Medium and Hard difficulty level problems. Let's get right to it.

Detect Cycles in a Directed Graph

Suppose you are given a directed graph, and you are asked to check if it contains a cycle or not. To solve this problem, before diving into the solution, let’s first know about the directed graphs and cycles. 

A graph whose edges allow only a certain direction of flow is known as a directed graph, or a graph having directed edges and a cycle in a directed graph is a non-empty trail with repeated first and last vertices.

directed graph

For example, the above graph contains the cycle: 1->5->4->0->1

Recommended to try the problem yourself first before moving on to the solution.

Solution using Depth First Search (DFS)

This approach takes the help of DFS Algorithm to detect cycles in a directed graph. We know that the DFS of a directed graph produces a DFS tree, which is a reordered representation of the edges and vertices of the graph. 

Now, this tree could have edges of different types, for example, forward edges, tree edges, cross edges, and back edges. So, before moving further, let’s have a brief introduction of these kinds of edges:

  • A forward edge is an edge that connects a node to its descendent without being a part of the DFS tree.
  • Tree edges are the edges obtained by the DFS traversal of the graph.
  • A cross edge is an edge that joins two vertices that don’t have a parent-child relationship among themselves.
  • A back edge is an edge that connects a vertex to its ancestor in the DFS tree, and if a DFS tree of a graph has a back edge, it contains a cycle, as the back edge will allow it to have a trail with repeated first and last nodes. 
     

We implement this by using an additional array that contains all the visited vertices and a recursion stack to keep track of the order of appearance of the vertices in the current recursion stack, which ultimately helps in backtracking. Let’s have a look at the DFS tree of the graph:

DFS tree of the graph

So, we will start with the DFS of the tree and check if we find a back edge in it. If yes, the graph has a cycle, and if not, the graph is acyclic.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm

  1. Take the number of edges and vertices as user input.
  2. Initialize the current index, visited, and recursion stack using recursion
  3. Mark the index in the recursion stack and the current node as visited.
  4. Make recursive calls (see recursion) for all the unvisited adjacent vertices for the current node, and if any of these recursive functions return true, return true as the final answer.
  5. If any adjacent vertices are already visited in the recursion stack, mark the answer as true.
  6. Return false if none of the above steps returns true.

Implementation of the solution

#include<bits/stdc++.h>
using namespace std;
//Class for the graph.
class graph
{
    int v;
    //Adjacency list.
    list<int> *adjacencylist;
    //Function to detectcycle.
    bool checkcycle2(int v, bool vertvisited[], bool *recursionst);
    public:
    graph(int v);
    void drawedge(int v, int u);
    bool checkcycle();
};
//Constructor for a graph with v nodes.
graph::graph(int v)
{
    this->v=v;
    adjacencylist= new list<int>[v];
}
//To add edges in the graph.
void graph::drawedge(int v, int u)
{
    adjacencylist[v].push_back(u);
}
//Function to keep track of visited nodes and recursion 
//stack.
bool graph::checkcycle2(int v, bool vertvisited[], bool *recursionst)
{
    if(vertvisited[v]==false)
    {
        //Marking the vertex as visited.
        vertvisited[v]=true;
        recursionst[v]=true;
        //Making recursive calls for the adjacent 
        //vertices and return true if any back edge is 
        //found.
        list<int>::iterator itr;
        for(itr=adjacencylist[v].begin();itr!=adjacencylist[v].end();++itr)
        {
            if(!vertvisited[*itr]&&checkcycle2(*itr, vertvisited, recursionst))
            {
                return true;
            }
            else if(recursionst[*itr])
            {
                return true;
            }
        }
    }
    //Unmark the vertex from recursion stack.
    recursionst[v]=false;
    return false;
}
bool graph::checkcycle()
{
    //Declare and initialise the visited and recursion stack array as false.
    bool *vertvisited=new bool[v];
    bool *recursionst=new bool[v];
    for(int i=0;i<v;i++)
    {
        vertvisited[i]=false;
        recursionst[i]=false;
    }
    //Call the "checkcycle2" function for cycle 
    //detection.
    for(int i=0;i<v;i++)
    {
        if(checkcycle2(i, vertvisited, recursionst))
        {
            return true;
        }
    }
    return false;
}
//Driver function.
int main()
{
    graph g(6);
    g.drawedge(0, 1);
    g.drawedge(1, 5);
    g.drawedge(5, 4);
    g.drawedge(4, 0);
    g.drawedge(4, 3);
    g.drawedge(3, 2);
    g.drawedge(0, 2);
    //Function call and print the result.
    if(g.checkcycle())
        cout << "Graph is cyclic";
    else
        cout << "Graph is acyclic";
    return 0;
}

 

Output

Graph is cyclic

Complexity Analysis

  • Time Complexity: The time complexity of the above approach to detect cycles in a directed graph is O(V+E), where V is the number of vertices in the graph and E is the number of edges. This happens because we are performing the DFS on the tree, which has the same time complexity.
  • Space Complexity: The space complexity of the above approach is O(V), where V is the number of vertices as we need to maintain a visited set and recursive stack.

Frequently Asked Questions

How do you determine if a directed graph has a cycle?

We can determine the cycle in a directed graph by looking at the DFS tree. If a directed graph has a back edge in its DFS tree, we can conclude that it contains a cycle.

What is a cycle in a directed graph?

A cycle in a directed graph is a trail with repeated first and last vertex. In a directed graph, if there is a path such that it starts and ends on the same node. Then, it is a cycle.

Does Dijkstra work for directed graph with cycles?

Yes, Dijkstra's algorithm works for directed graphs that have cycles. In order for Dijkstra's algorithm to not work, the graph should contain a negative cycle or negative weights else, Dijkstra's algorithm works fine.

Can we detect cycle using BFS?

Yes, we can detect a cycle in a directed graph using BFS. We have to use the concept of Topological sort using BFS. Since a valid topological sort can be found for only a Directed Acyclic Graph, if no valid topological sort is found, the graph contains a cycle.

Conclusion

In this blog, we have discussed one of the methods to detect cycles in a directed graph.

The idea is to do a DFS traversal of the graph and maintain an array of visited vertices. During the DFS traversal, if we find a back edge, i.e., an edge that connects back to an already visited verified, we will return the answer that the graph is cyclic. Here we maintained two arrays of vertices, one for keeping track of the visited vertices and the other for the recursion call stack for the DFS traversal. 

Recommended Reading:

Want to solve more problems? Check these out:

 

Check out some of the amazing Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingBasics of C, Basics of JavaOperating SystemsComputer Networks, etc., along with some Contests and Test Series only on Coding Ninjas StudioEnrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations. 

Do upvote our blog to help other ninjas grow. 

Happy Learning, Ninja!

Happy Coding!!

Topics covered
1.
Introduction
2.
Solution using Depth First Search (DFS)
3.
Algorithm
3.1.
Implementation of the solution
3.2.
Output
4.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
How do you determine if a directed graph has a cycle?
5.2.
What is a cycle in a directed graph?
5.3.
Does Dijkstra work for directed graph with cycles?
5.4.
Can we detect cycle using BFS?
6.
Conclusion
6.1.
Recommended Reading:
6.2.
Want to solve more problems? Check these out: