Last Updated: 14 May, 2021
Detect Cycle in a Directed Graph
Easy
Asked in companies
Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false.
Input Format:
The first line of input contains an integer T, the number of test cases.
The first line of each test case contains two single space-separated integers ‘V’, and ‘E’. ‘V’ represents the number of nodes and ‘E’ represents the number of edges in the graph.
From the second line onwards of each test case, the next 'E' lines will denote the edges of the graph where every edge is defined by two single space-separated integers 'A' and 'B', which signifies an edge from vertex 'A’ to vertex 'B'.
Output Format:
For each test case print "true" if a cycle exists, else "false".
Constraints:
1 <= T <= 10
1 <= V <= 10^3
0 <= E <= 10^3
0 <= A, B < V
Time Limit: 1sec
Approaches
To change a directed tree to a cyclic directed graph by adding one edge, we can choose a node that has more than zero ancestors and add an edge from that node to one of its ancestors. This can always form a complete cycle. This edge is called the back edge.
The basic idea is to traverse a graph using DFS and keep track of visited nodes and search for the back edge. If we found any back edge, we will return true, else we will return false.
DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. 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.
To detect a back edge, we can use coloring to keep track of visited nodes as well as ancestors. The color “0” represents an unvisited node. All the nodes with the color “1” represent the ancestor of the node. The color “2” represents visited nodes that are not ancestors of the node. We can traverse the graph using DFS and for each node, we check if there is any back edge that connects to its ancestor with color “1”. If we find any back edge then return true otherwise return false.
For a disconnected graph, we run the same algorithm of each connected graph and return true if there is a back edge in any of the connected graphs.
Algorithm:
- Insert all the edges in the graph and make an adjacency list “graph”.
- Initialize an array “color” with all the values “0” representing unvisited nodes.
- Iterate over the nodes and for each unvisited node with color “0”: traverse the graph using DFS. If DFS returns true then there is a back edge in the graph. So return true.
- Consider the recursive function “DFS” that takes three arguments, “U” represents the node number, “color” represents the color of the nodes, “graph” represents the adjacency list.
- In DFS, first color the node “U” with 1, which represents the node “U” will be the ancestor of the future nodes.
- Iterate over all adjacent nodes “V”:
- If the color of node “V” is 1, that means “V” is the ancestor of “U”, that also means the edge from “U” to “V” is the back edge which forms a cycle. So return true.
- If the color of node “V” is 0, make a recursive call on node “V” to check for a back edge in the subtree of “V”. if there is a back edge then return true.
- If there we can not find the back edge, return false.
- Otherwise, return false.