javascript-spec / buildout-loud-hacktober

Learn DSA this October with Hacktoberfest 2022
1 stars 9 forks source link

[added]: Detect Cycle in a Directed Graph #14

Closed cuteipie closed 1 year ago

cuteipie commented 1 year ago

There is a cycle in a graph only if there is a back edge present in the graph. Depth First Traversal can be used to detect a cycle in a Graph, DFS for a connected graph produces a tree.

If the graph is disconnected then get the DFS forest and check for a cycle in individual trees by checking back edges. To detect a back edge, keep track of vertices currently in the recursion stack of function for DFS traversal. If a vertex is reached that is already in the recursion stack then there is a cycle in the tree

asv02 commented 1 year ago

@javascript-spec I can give an efficient solution with proper explanation, please assign it to me.