Graph – Detect Cycle in a Directed Graph

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.

Use DFS(Depth-First Search) to detect the back edge

  • Do the DFS from each vertex
  • For DFS from each vertex, keep track of visiting vertices in a recursion stack (array).
  • If you encounter a vertex which already present in recursion stack then we have found a cycle.
  • Use visited[] for DFS to keep track of already visited vertices.

How different is recursion stack[] from visitied [].

  • Visited[] is used to keep track of already visited vertices during the DFS is never gets
  • Recursion stack[] is used from keep track of visiting vertices during DFS from particular vertex and gets reset once cycle is not found from that vertex and will try DFS from other vertices.
  • See the code from more understanding.

Time Complexity: O(V+E)

Code:

import java.util.LinkedList;
public class DGCycle {
static class Graph {
int vertices;
LinkedList<Integer>[] adjList;
Graph(int vertices) {
this.vertices = vertices;
adjList = new LinkedList[vertices];
for (int i = 0; i < vertices; i++) {
adjList[i] = new LinkedList<>();
}
}
public void addEgde(int source, int destination) {
adjList[source].addFirst(destination);
}
public boolean isCycle() {
boolean visited[] = new boolean[vertices];
boolean recursiveArr[] = new boolean[vertices];
//do DFS from each node
for (int i = 0; i < vertices; i++) {
if (isCycleUtil(i, visited, recursiveArr))
return true;
}
return false;
}
public boolean isCycleUtil(int vertex, boolean[] visited, boolean[] recursiveArr) {
visited[vertex] = true;
recursiveArr[vertex] = true;
//recursive call to all the adjacent vertices
for (int i = 0; i < adjList[vertex].size(); i++) {
//if not already visited
int adjVertex = adjList[vertex].get(i);
if (!visited[adjVertex] && isCycleUtil(adjVertex, visited, recursiveArr)) {
return true;
} else if (recursiveArr[adjVertex])
return true;
}
//if reached here means cycle has not found in DFS from this vertex
//reset
recursiveArr[vertex] = false;
return false;
}
}
public static void main(String[] args) {
int vertices = 4;
Graph graph = new Graph(vertices);
graph.addEgde(0, 1);
graph.addEgde(1, 2);
graph.addEgde(2, 3);
graph.addEgde(3, 1);
boolean result = graph.isCycle();
System.out.println("is Cycle present: " + result);
}
}

view raw
DGCycle.java
hosted with ❤ by GitHub


Output:

is Cycle present: True