**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:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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)