Given a directed graph with "v" vertices (0 to v-1), check whether the graph contains a cycle or not.
Solutions
Method 1: Using BFS
The idea is to simply use Kahn’s algorithm for Topological Sorting.
If count of visited nodes is not equal to the number of nodes in the graph has cycle, otherwise not.
Complexity
The time complexity of this solution is O(v+e) and space complexity is O(v).
Method 2: Using DFS
If the graph is disconnected, then check for a cycle in individual trees (start from each non-visited node).
Start traversing the graph in a DFS manner and keep track of visited nodes in two different arrays, visited[] and visitedSameRecur[].
The visited[] array keeps track of overall visited nodes throughout the graph, while visitedSameRecur[] keeps track of visited nodes in the current recursion.
Once a node is visited twice in the same recursion (visitedSameRecur[]), return "true".
Note: The second array "visitedSameRecur[]" is needed to avoid situations where one node is visited twice, yet it does not form a cycle, as shown in the picture above. Although "4" is visited twice, each time with a different recursion, nodes "2, 3, 4, 5" do not form a cycle.
Complexity
The time complexity of this solution is O(v+e) and space complexity is O(v).