**Objective**: Given a directed graph write an algorithm to find out whether graph contains cycle or not.

**Example**:

**Approach**:

Graph contains cycle if there are any back edges. There are two types of back edges as seen in the example above (marked in red)

- Edge from a vertex to itself. Self loop. (4-4)
- Edge from any descendent back to vertex.

Earlier we have seen detect cycle using recursion stack. In this article we will how to use colors to detect cycle in graphs.

**Using Colors:**

We will assign every vertex a color and will use 3 colors- white, gray and black.

**White Color:**Vertices which are not processed will be assigned white colors. So at the beginning all the vertices will be white.**Gray Color:**Vertices will are currently being processed. If DFS(Depth-First Search) is started from a particular vertex will be in gray color till DFS is not completed (means all the descendants in DFS are not processed.)**Black Color:**Vertices for which the DFS is completed, means all the processed vertices will be assigned black color.**Cycle Detection:**During DFS if we encounter a vertex which is already in Gray color (means this vertex already in processing and in Gray color in the current DFS) then we have detected a Cycle and edge from current vertex to gray vertex will a back edge.**Example**– Graph 2->3->4->2. Start DFS from vertex 2 (make it gray). Then vertex 3 and 4 will be in processing (Gray color) and when 4->2 will be in processing, vertex 2 needs to be colored in gray but vertex 2 is already in gray color, means cycle is detected.

See the animation below for more understanding.

**Code:**

import java.util.HashSet; | |

import java.util.LinkedList; | |

public class DirectedGraphCycleColors { | |

static class Graph { | |

int vertices; | |

LinkedList<Integer>[] adjList; | |

public Graph(int vertices) { | |

this.vertices = vertices; | |

adjList = new LinkedList[vertices]; | |

for (int i = 0; i < vertices; i++) { | |

adjList[i] = new LinkedList<>(); | |

} | |

} | |

public void addEdge(int source, int destination) { | |

//add forward edge | |

adjList[source].addFirst(destination); | |

} | |

public boolean isCycle() { | |

//Create color sets | |

HashSet<Integer> whiteSet = new HashSet<>(); | |

HashSet<Integer> graySet = new HashSet<>(); | |

HashSet<Integer> blackSet = new HashSet<>(); | |

//Initially put all vertices in White set | |

for (int i = 0; i <adjList.length ; i++) { | |

whiteSet.add(i); | |

} | |

//traverse only white vertices | |

for (int i = 0; i <vertices ; i++) { | |

if(whiteSet.contains(i) && | |

isCycleUtil(i,whiteSet,graySet,blackSet)){ | |

return true; | |

} | |

} | |

return false; | |

} | |

public boolean isCycleUtil(int vertex, HashSet<Integer> whiteSet, HashSet<Integer> graySet, HashSet<Integer> blackSet){ | |

//visiting this vertex, make it gray from white | |

whiteSet.remove(vertex); | |

graySet.add(vertex); | |

//visit neighbors | |

for (int i = 0; i <adjList[vertex].size() ; i++) { | |

int adjVertex = adjList[vertex].get(i); | |

//check if this vertex is present in gray set, means cycle is found | |

if (graySet.contains(adjVertex)) | |

return true; | |

//check if this vertex is present in black set, means this vertex is already done | |

if (blackSet.contains(adjVertex)) | |

continue; | |

//do traversal from this vertex | |

if (isCycleUtil(adjVertex, whiteSet, graySet, blackSet)) | |

return true; | |

} | |

//if here means cycle is not found from this vertex, make if black from gray | |

graySet.remove(vertex); | |

blackSet.add(vertex); | |

return false; | |

} | |

} | |

public static void main(String[] args) { | |

int vertices = 5; | |

Graph graph = new Graph(vertices); | |

graph.addEdge(0, 1); | |

graph.addEdge(0, 2); | |

graph.addEdge(1, 3); | |

graph.addEdge(3, 0); | |

graph.addEdge(3, 4); | |

boolean result = graph.isCycle(); | |

System.out.println("is Cycle present: " + result); | |

} | |

} |

**Output: **

is Cycle present: true

What is the time complexity of this algo ?

Since we traversing each vertex and edge only once so the time complexity is O(V+E)