Detect Cycle in a Directed Graph (Using BFS or DFS)

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.

The time complexity of this solution is O(v+e) and space complexity is O(v).

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.

The time complexity of this solution is O(v+e) and space complexity is O(v).