Java program to find a cycle in undirected graph

package com.sample.app.model;

import java.util.List;

public class Vertex<T extends Comparable<T>> {
 private int id;
 private List<T> adjacentVertices;

 public int getId() {
  return id;
 }

 public void setId(int id) {
  this.id = id;
 }

 public List<T> getAdjacentVertices() {
  return adjacentVertices;
 }

 public void setAdjacentVertices(List<T> adjacentVertices) {
  this.adjacentVertices = adjacentVertices;
 }

}

package com.sample.app.model;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class UnDirectedGraph <T extends Comparable<T>> {
 private Map<T, Set<T>> graph;
 private Map<T, Boolean> visited = new HashMap<>();

 private Set<T> distinctVertices = new HashSet<>();;

 public UnDirectedGraph() {
  graph = new HashMap<>();
 }

 public void addEdge(T from, T to) {

  Set<T> adjacencyList = graph.get(from);

  if (adjacencyList == null) {
   adjacencyList = new HashSet<T>();
  }

  adjacencyList.add(to);

  graph.put(from, adjacencyList);
  distinctVertices.add(from);
  distinctVertices.add(to);
 }

 public Map<T, Set<T>> getGraph() {
  return graph;
 }

 public void setGraph(Map<T, Set<T>> graph) {
  this.graph = graph;
 }
 
 private Boolean isCyclicUtil(T v, Map<T, Boolean> visited, T parent) {

  visited.put(v, true);
  T i;

  Set<T> adjacencyList = graph.get(v);

  if (adjacencyList == null || adjacencyList.isEmpty())
   return false;

  Iterator<T> it = adjacencyList.iterator();
  while (it.hasNext()) {
   i = it.next();

   if (!visited.get(i)) {
    if (isCyclicUtil(i, visited, v))
     return true;
   }

   else if (!i.equals(parent))
    return true;
  }
  return false;
 }

 public boolean isCycleExist() {

  for (T key : distinctVertices) {
   visited.put(key, false);

  }

  for (T key : this.graph.keySet())
   if (!visited.get(key))
    if (isCyclicUtil(key, visited, null))
     return true;

  return false;

 }

}

package com.sample.app.model;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

import org.junit.Test;


public class UndirectedGraphTest {

 @Test
 public void testCase1() {
  UnDirectedGraph g1 = new UnDirectedGraph<Integer>();

  g1.addEdge(1, 0);
  g1.addEdge(0, 2);
  g1.addEdge(2, 1);
  g1.addEdge(0, 3);
  g1.addEdge(3, 4);

  assertTrue(g1.isCycleExist());
 }

 @Test
 public void testCase2() {
  UnDirectedGraph g1 = new UnDirectedGraph<Integer>();

  g1.addEdge(0, 1);
  g1.addEdge(1, 2);

  assertFalse(g1.isCycleExist());
 }

 @Test
 public void testCase3() {
  UnDirectedGraph g1 = new UnDirectedGraph<Integer>();

  assertFalse(g1.isCycleExist());
 }

 @Test
 public void testCase4() {
  UnDirectedGraph g1 = new UnDirectedGraph<Integer>();

  g1.addEdge(123, 0);
  g1.addEdge(0, 123);
  g1.addEdge(4232, 123);
  g1.addEdge(0, 3);
  g1.addEdge(3, 4);

  assertTrue(g1.isCycleExist());
 }

 @Test
 public void testCase5() {
  UnDirectedGraph g1 = new UnDirectedGraph<Integer>();

  g1.addEdge(1, 1);

  assertTrue(g1.isCycleExist());
 }

 @Test
 public void testCase6() {
  UnDirectedGraph g1 = new UnDirectedGraph<Integer>();

  g1.addEdge(1, 2);
  g1.addEdge(1, 1);

  assertTrue(g1.isCycleExist());
 }

 @Test
 public void testCase7() {
  UnDirectedGraph g1 = new UnDirectedGraph<Integer>();

  g1.addEdge(1, 2);
  g1.addEdge(1, 3);
  g1.addEdge(2, 3);

  assertTrue(g1.isCycleExist());
 }

 @Test
 public void testCase8() {
  UnDirectedGraph g1 = new UnDirectedGraph<Integer>();

  g1.addEdge(1, 2);
  g1.addEdge(1, 3);
  g1.addEdge(2, 3);
  g1.addEdge(3, 1);

  assertTrue(g1.isCycleExist());
 }

 @Test
 public void testCase9() {
  UnDirectedGraph g1 = new UnDirectedGraph<Integer>();

  g1.addEdge(1, 2);
  g1.addEdge(1, 3);
  g1.addEdge(2, 3);
  g1.addEdge(3, 4);
  g1.addEdge(3, 5);
  g1.addEdge(5, 2);

  assertTrue(g1.isCycleExist());
 }
}

You may like

Design Patterns

Interview Questions

Programming Questions

Find the permutations of a string

Add element to the end of stack

Reverse the elements of stack

Suppose there are 'N' stairs, a person wants to reach the top. Person can climb either 1 (or) 2 stairs at a time.Count the number of ways that a person can reach the top.         

Find cycle in a directed graph