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
Java program to Detect Cycle in an Undirected Graph
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
Java program to Detect Cycle in an Undirected Graph

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

Your email address will not be published. Required fields are marked *