Detect Cycle in Directed Graph in O(V+E)

 

Introduction 

In this article, we will learn about Detect Cycle in Directed Graph using multiple approaches. 

Examine a directed graph to see if it has a cycle. If the given graph contains at least one cycle, your function should return true; otherwise, it should return false.

Method 1:

DFS Approach

A cycle in a graph can be detected using Depth First Traversal. A tree is produced using DFS for a connected graph. Only if the graph has a rear edge does it have a cycle. A back edge in the DFS tree is an edge that connects a node to itself (self-loop) or one of its ancestors.

Get the DFS forest as output for a disconnected graph. Check for a cycle in individual trees by looking at the back borders.

Keep track of the vertices currently in the recursion stack of the DFS traversal algorithm to detect a back edge. There is a cycle in the tree if a vertex is reached that is already on the recursion stack. A back edge connects the current vertex to the next vertex in the recursion stack. To keep track of vertices in the recursion stack, use the recStack[] array.

Algorithm:

• Create the graph using the given number of edges and vertices.
• Create a recursive function that initializes the current index or vertex, visited, and recursion stack.
• Mark the current node as visited and also mark the index in the recursion stack.
• Find all the vertices which are not visited and are adjacent to the current node. Recursively call the function for those vertices, If the recursive function returns true, return true.
• If the adjacent vertices are already marked in the recursion stack then return true.
• Create a function, that calls the recursive function for all the vertices, and if any function returns true return true. Else if for all vertices the function returns false return false.

read more...