DetectCycleDirectedGraph.java

packageGraph;

importjava.util.ArrayList;

publicclassDetectCycleDirectedGraph {

publicstaticvoidmain(String[] args) {

inttotalVertices = 4; // test graph 1
ArrayList<ArrayList<Integer>> adjList = newArrayList<ArrayList<Integer>>(totalVertices);
for (inti = 0; i < totalVertices; i++) {
adjList.add(newArrayList<Integer>());
 }

// test graph 1, cycle - true

// addEdge(adjList, 0, 1);
// addEdge(adjList, 1, 2);
// addEdge(adjList, 2, 3);
// addEdge(adjList, 3, 1);

// test graph 2, cycle - false

addEdge(adjList, 0, 1);
addEdge(adjList, 2, 1);
addEdge(adjList, 2, 3);
addEdge(adjList, 1, 3);

display(adjList);
System.out.println("\nhas cycle: " + hasCycleDirected(adjList));

 }

privatestaticvoidaddEdge(ArrayList<ArrayList<Integer>> adjList, intu, intv) {
adjList.get(u).add(v);
// adjList.get(v).add(u);
 }

publicstaticvoiddisplay(ArrayList<ArrayList<Integer>> adjList) {
for (inti = 0; i < adjList.size(); i++) {
System.out.println(i + ": " + adjList.get(i));
 }
 }

// O(V+E) Time
privatestaticbooleanhasCycleDirected(ArrayList<ArrayList<Integer>> adjList) {
returndepthFirstTraverse(adjList);
 }

privatestaticbooleandepthFirstTraverse(ArrayList<ArrayList<Integer>> adjList) {

boolean[] visited = newboolean[adjList.size()];

// to track 'Back Edge' in recursion stack
boolean[] recursionStack = newboolean[adjList.size()];

for (inti = 0; i < adjList.size(); i++) {

if (visited[i] == false) {

if (dfsRecursion(adjList, i, visited, recursionStack)) {
returntrue;
 }
 }
 }
returnfalse;
 }

privatestaticbooleandfsRecursion(ArrayList<ArrayList<Integer>> adjList, intsrc, boolean[] visited,
boolean[] recursionStack) {

visited[src] = true;
recursionStack[src] = true; // src currently in recursive call stack

for (Integerneighbor : adjList.get(src)) {

if (visited[neighbor] == false) {
if (dfsRecursion(adjList, neighbor, visited, recursionStack) == true) {
returntrue; // cycle exists
 }
 } elseif (recursionStack[neighbor] == true)
returntrue;
 }
recursionStack[src] = false; // src is now removed from the call stack

returnfalse;
 }
}