CC-5 : Check if the graph contains a cycle path.

Description:

Check if the graph contains a cycle path.

Test cases and expected outputs:

Input Parameters	Expected outputs
GraphCheckCycle gph=new GraphCheckCycle(4); gph.addEdge(0, 1); gph.addEdge(0, 2); gph.addEdge(0, 3); gph.displayGraph(); retVal=gph.checkCycle(); System.out.println("Does Graph have cycle: "+retVal);	vertex 0->1->2->3 vertex 1->0 vertex 2->0 vertex 3->0 Does Graph have cycle: false
gph=new GraphCheckCycle(3); gph.addEdge(0, 1); gph.addEdge(0, 2); gph.addEdge(1, 2); gph.displayGraph(); retVal=gph.checkCycle(); System.out.println("Does Graph have cycle: "+retVal);	vertex 0->1->2 vertex 1->0->2 vertex 2->0->1 Does Graph have cycle: true

Pseudocode:

Initialize an int variable named visited to store information whether a particular vertice in the graph has been visited.

Method checkCycle():

Iterate through vertices using a for loop with iIdx as loop variable with values from 0 to number of vertices in the graph :

If visited[iIdx] is not 1, then:

Call checkCycleRecurive(iIdx).

If return value from checkCycleRecursive() method is true, the graph contains a cycle path, else it does not contain a cycle path.

Method checkCycleRecursive(vertice, parent):

Set visited[vertice] to 1 as the vertice has been visited.

Extract vertices connected to input vertice from the adjacencyList.

Iterate through vertices connected to input vertice using iterator:

Set variable adjacentNode to point to current connected vertice.

If visited[adjacentNode] is not 1, then:

Call checkCycleRecursive(adjacentNode, vertice) recursively.

If return value from checkCycleRecursive() method is true, the graph contains a cycle path, else it does not contain a cycle path.

Else:

If adjacentNode != its parent, return true.

Code:

public class GraphCheckCycle {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public GraphCheckCycle(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 adjacencyLists.get(dest).add(source);
 }
 
 public boolean checkCycle() {
	 for (int idx=0; idx < vertices; idx++) {
		 if (visited[idx]==0) {
			if ( checkCycleRecursive(idx, -1) == true) {
				return true;
			}
		 }
	 }
	 return false;
 }
 
 
 public boolean checkCycleRecursive(int vertice, int parent) {
	 visited[vertice]=1;
	 ArrayList<Integer> adjacentNodes=adjacencyLists.get(vertice);
	 for (int idx=0; idx < adjacentNodes.size(); idx++) {
		 int adjNode=adjacentNodes.get(idx);
		 if (visited[adjNode]==0) {
			 if (checkCycleRecursive(adjNode, vertice)==true) {
				return true;				 
			 }
		 } else {
			 if (adjNode != parent) {
				 return true;
			 }
		 }
	 }
	 return false; 
 } 
 
 }

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.ArrayList;
import java.util.Iterator;

public class GraphCheckCycle {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public GraphCheckCycle(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 adjacencyLists.get(dest).add(source);
 }
 
 public void dfsTraversal(int vertex) {
	  visited[vertex]=1;
	 dfsTraversal+= vertex + " ";
	 Iterator<Integer> itr=adjacencyLists.get(vertex).iterator();
	 while (itr.hasNext()) {
		 int adjacentNode=itr.next();
		 if (visited[adjacentNode]==0) {
			 dfsTraversal(adjacentNode);
		 }
	 }	
 }
 
 public boolean checkCycle() {
	 for (int idx=0; idx < vertices; idx++) {
		 if (visited[idx]==0) {
			if ( checkCycleRecursive(idx, -1) == true) {
				return true;
			}
		 }
	 }
	 return false;
 }
 
 
 public boolean checkCycleRecursive(int vertice, int parent) {
	 visited[vertice]=1;
	 ArrayList<Integer> adjacentNodes=adjacencyLists.get(vertice);
	 for (int idx=0; idx < adjacentNodes.size(); idx++) {
		 int adjNode=adjacentNodes.get(idx);
		 if (visited[adjNode]==0) {
			 if (checkCycleRecursive(adjNode, vertice)==true) {
				return true;				 
			 }
		 } else {
			 if (adjNode != parent) {
				 return true;
			 }
		 }
	 }
	 return false; 
 } 
 
 public void displayGraph() {
	 for (int iIdx=0;iIdx< adjacencyLists.size();iIdx++) {
		 System.out.println();
		 System.out.print("vertex "+iIdx);
		 for (int jIdx=0;jIdx< adjacencyLists.get(iIdx).size();jIdx++) {
			 System.out.print("->"+adjacencyLists.get(iIdx).get(jIdx));
		 }
	 }
 }
 


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	boolean retVal;
	try {
	GraphCheckCycle gph=new GraphCheckCycle(4);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.displayGraph();
	retVal=gph.checkCycle();
	System.out.println();
	System.out.println("Does Graph have cycle: "+retVal);	
	
	gph=new GraphCheckCycle(3);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(1, 2);
	gph.displayGraph();
	retVal=gph.checkCycle();
	System.out.println();
	System.out.println("Does Graph have cycle: "+retVal);
	
	gph=new GraphCheckCycle(5);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.addEdge(3, 4);
	gph.addEdge(4, 0);
	gph.displayGraph();
	retVal=gph.checkCycle();
	System.out.println();
	System.out.println("Does Graph have cycle: "+retVal);	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}