Detect Cycle in a Directed Graph
Given a directed graph, check whether the graph contains a cycle or not
Solution:
- Loop can be detected by DFS traversal
- If there is loop then there will be back edge,
- A Back edge – is a edge that is from a node to itself (selfloop) or one of its ancestors in the tree produced by DFS.
-
- To detect a back edge – We will use local visited boolean will set true before each stack call and set false end of stack call.
Latest Source Code:
Github: LoopDetectorInDirectedGraph.java
Output:
Graph: 0 -> [1, 2] 1 -> [2] 2 -> [0, 3] 3 -> [3] Is loop exists: true