Detect Cycle in a Directed Graph

Solution:

• Algorithm is based on 3 different buckets (white-bucket gray-bucket and black-bucket)
  1. White Bucket – means vertices are not visited
  2. Gray Bucket – means vertices are under process
  3. Black Bucket – means vertices are processed

Algorithm:

1. Create three lists (buckets)
   1. White Bucket – means vertices are not visited
   2. Gray Bucket – means vertices are under process
   3. Black Bucket – means vertices are processed
2. Add all vertices to White Buckets
3. Iterate till white bucket is not empty
4. Call Modified DFS
5. In Modified DFS Function
   1. Move vertex from white bucket to gray bucket
   2. Iterate all adjacent_vertices of current vertex
      1. If adjacent_vertex is in back bucket then
         1. don’t do anything
      2. Else if adjacent_vertex is in gray bucket then
         1. return true (means there is loop)
      3. Else
         1. recursively call modified DFS for adjacent_vertex
   3. Move vertex from gray bucket to black bucket
   4. Return false

Source Code:
Github: CycleDetectInDirectedGraph.java

Output:

 

V(0), Adjacent vertices: [1, 2]
V(1), Adjacent vertices: [2]
V(2), Adjacent vertices: [0, 3]
V(3), Adjacent vertices: [3]

Is loop found: true

Video