# Java program to Detect Cycle in an Undirected Graph

In this tutorial, you will learn how to detect if a cycle exists in an undirected graph in Java without using any complex cycle-detection algorithms.

## Detection of a cycle in an undirected graph in Java

**What is an undirected graph?**

Let`s start off by knowing what an *undirected graph *is, A graph in which all the nodes are connected together with bi-directional edges is called an undirected graph. For example, observe the graph below

Each node in the graph is connected with the other nodes with a *bi-directional* edge i.e, an edge that defines the existence of a connection from Node A to B as well as Node B to A.

So in our diagram above

Node 1 is connected to 2 and Node 2 is connected to 1

Node 1 is connected to 3 and Node 3 is connected to 1

Node 2 is connected to 3 and Node 3 is connected to 2

Node 2 is connected to 1 and Node 1 is connected to 2

Node 3 is connected to 2 and Node 2 is connected to 3

Node 3 is connected to 1 and Node 1 is connected to 3

**How do we represent graphs**

Graphs can be represented either by adjacency matrix or by adjacency list, adjacency list is generally preferred because of its less space complexities.

**Detection of cycle in an undirected graph**

Since our objective is just to detect if a cycle exists or not, we will not use any cycle detection algorithm, rather we will be using a simple property between *number of nodes *and *number of edges *in a graph, we can find those out by doing a simple DFS on the graph.

For more coverage on DFS visit this link: How to perform Depth First Search in Java?

The idea being is, for every undirected cyclic graph the following property holds **If the total number of nodes in the graph -1 != (The total number of components)/2 **, then the graph is cyclic.

**Code
**

import java.io.*; import java.util.*; public class Solution { //The hashset gives us the total number //of nodes in a graph. public static HashSet<Integer> hs; public static int dfs(ArrayList<ArrayList<Integer>> g,int s,boolean vis[]){ //classic DFS function hs.add(s); int ans=g.get(s).size(); vis[s]=true; for(int ele:g.get(s)){ //If we encounter a node //that has not been visited //before,we recursively call //DFS from that node. if(!vis[ele]){ ans+=dfs(g,ele,vis); } } return ans; } public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter the number of nodes and edges"); String[] str=br.readLine().split(" "); int n=Integer.parseInt(str[0]); int m=Integer.parseInt(str[1]); ArrayList<ArrayList<Integer>> g=new ArrayList<>(); for(int i=0;i<=n;i++){ g.add(new ArrayList<Integer>()); } System.out.println("Enter "+m+" edges"); for(int i=0;i<m;i++){ String[] str1=br.readLine().split(" "); int s=Integer.parseInt(str1[0]); int d=Integer.parseInt(str1[1]); g.get(s).add(d); g.get(d).add(s); } int cnt=0; int vertices=0; int edges=0; String ans=""; boolean flag=true; boolean vis[]=new boolean[n+1]; for(int j=1;j<=n;j++){ if(vis[j]==false){ hs=new HashSet<Integer>(); int an=dfs(g,j,vis); //If the below property does not hold // then cycle exists so, we set //the flag to false if(hs.size()-1!=an/2) flag=false; } } if(flag) System.out.println("Cycle does not exist"); //If the flag is not set to false //then cycle exists else System.out.println("Cycle exists"); } }

Output

`Enter the number of nodes and edges`

3 3

`Enter 3 edges`

0 1 1 2 2 0

`Cycle exists`

The graph looks like this

The number of nodes here is 3 (0,1,2)

Number of components is 6

0–1

0–2 (2–0)

1–0 (0–1)

1–2

2–0

2–1 (1–2)

Nodes -1 == 2

Components/2 == 6/2 == 3

2 != 3

Since the property holds, we can say that a cycle exists!

## Leave a Reply