DetectCycleUndirectedGraph.java

packageGraph;

importjava.util.ArrayList;

publicclassDetectCycleUndirectedGraph {

privatestaticbooleanhasCycle(ArrayList<ArrayList<Integer>> adjList) {
returndepthFirstTraverse(adjList);
 }

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

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

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

if (visited[i] == false) {

intisParent = -1;
if (dfsRecursion(adjList, i, visited, isParent) == true) {
returntrue;
 }
 }
 }
returnfalse;
 }

privatestaticbooleandfsRecursion(ArrayList<ArrayList<Integer>> adjList, intsrc, boolean[] visited, intparent) {
visited[src] = true;

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

if (visited[neighbor] == false) {

if (dfsRecursion(adjList, neighbor, visited, src) == true) {
returntrue; // cycle exists
 }
 } elseif (neighbor != parent)
returntrue;
 }
returnfalse;
 }

publicstaticvoidmain(String[] args) {

// int totalVertices = 6; // test graph 1
// int totalVertices = 5; // test graph 2
inttotalVertices = 4; // test graph 3

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, 1, 3);
// addEdge(adjList, 3, 2);
// addEdge(adjList, 2, 4);
// addEdge(adjList, 4, 5);

// test graph 2, cycle - false

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

// test graph 3, cycle - true

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

System.out.println("adjacency list representation of Graph\n");
display(adjList);

System.out.println("\nhas cycle: " + hasCycle(adjList)); // 2
 }

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));
 }
 }
}