Graph – Detect Cycle in a Directed Graph using colors

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)

  1. Edge from a vertex to itself. Self loop. (4-4)
  2. 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.

 
1/9
2/9
3/9
4/9
5/9
6/9
7/9
8/9
9/9
previous arrow
PlayPause
next arrow

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

2 thoughts on “Graph – Detect Cycle in a Directed Graph using colors”

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.