### Detect Cycle in a Directed Graph

**Solution:**

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

##### Algorithm:

- Create three lists (buckets)
- White Bucket – means vertices are not visited
- Gray Bucket – means vertices are under process
- Black Bucket – means vertices are processed

- Add all vertices to White Buckets
- Iterate till white bucket is not empty
- Call Modified DFS
- In
**Modified DFS Function**- Move vertex from white bucket to gray bucket
- Iterate all adjacent_vertices of current vertex
- If adjacent_vertex is in back bucket then
- don’t do anything

- Else if adjacent_vertex is in gray bucket then
- return true (means there is loop)

- Else
- recursively call modified DFS for adjacent_vertex

- If adjacent_vertex is in back bucket then
- Move vertex from gray bucket to black bucket
- 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