Algorithm
- Take the number of edges and vertices as user input.
- Initialize the current index, visited, and recursion stack using recursion
- Mark the index in the recursion stack and the current node as visited.
-
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.
-
If any adjacent vertices are already visited in the recursion stack, mark the answer as true.
- 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;
}
You can also try this code with Online C++ Compiler
Output
Graph is cyclic
You can also try this code with Online C++ Compiler
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 Algorithms, Competitive Programming, Basics of C, Basics of Java, Operating Systems, Computer Networks, etc., along with some Contests and Test Series only on Coding Ninjas Studio. Enrol 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!!
19+ registered 
