Graph Algorithm — Cycle Detection in Directed Graph using DFS
What is a Cycle
In graph theory, a path that starts from a given node and ends on the same node is a cycle.
Cycle Detection in an Directed Graph
A directed graph is a set of objects, otherwise called vertices or nodes, connected together and all the edges are directed from one vertex to another.
A directed graph is an ordered pair G = (V, E) where,
V is a set of elements known as vertices or nodes.
E is a set of ordered pair of vertices called as edges or directed edges.
Cycle in a directed graph can be detected with the help of Depth-First Search algorithm.
DFS Algorithm for Cycle Detection in an Directed Graph
The dfs algorithm for cycle detection in undirected graph will not work here because we cannot say that directed graph is having a cycle, if we get to a node which is already marked as visited and previous node is different.
📌 Initialise a visited boolean array with all nodes unvisited, a boolean recursion stack with all nodes set to false.
A recursion stack is to track the nodes that are currently in recursion. We mark node as true if the node has further recursion calls and change it to false for no recursion calls.
📌 Run a loop from 0 to n — 1 as the graph may have different components.
📌 If the current node is not visited, call the dfs recursive function passing the current node, visited array, recursion stack array.
dfs(graph, node, visited, recursionStack)
📌 Inside the dfs function, check if the node is already in the recursion stack.
If it is already in the recursion stack, this means we are going to repeat the recursion call which results in a cycle. So we detect cycle in graph and return true.
📌 Check if the node is already visited. If yes, return false.
📌 Mark the node as visited and mark the node in recursion stack.
📌 Traverse through the children of the current node.
📌 Continue doing the recursion for all the children.
📌 If the recursion calls for the current node is over, reset the value to false in the recursion stack array.
📌 If we get out of the initial for loop and all the nodes are now visited, this means we have no cycle.
Example
- A Directed Graph with No Cycle.
2. A Directed Graph with Cycle.
Time and Space Complexity
- We are traversing through all the nodes and edges. So time complexity will be O(V + E) where V = vertices or node, E = edges.
- We use a visited array, recursion stack array and an adjacency list for the graph. So the space complexity will be O(V) + O(V) + O(V + E) + extra space for the recursion calls.
Code
