dsa/Graphs/CycleDetectionBFS.java

import java.util.*;
import java.io.*;

class Main {

    // helper structure
    static class Node{
        int node;
        int parent;

        Node(int node, int parent){
            this.node = node;
            this.parent = parent;
        }
    }

    public static boolean bfs(int src, int V,
                              ArrayList<ArrayList<Integer>> adj,
                              boolean visited[]){

        visited[src] = true;

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(src, -1));

        while(!q.isEmpty()){
            Node cur = q.poll();
            int u = cur.node;
            int par = cur.parent;

            for(int v : adj.get(u)){
                if(!visited[v]){
                    visited[v] = true;
                    q.add(new Node(v, u));
                }
                else if(v != par){
                    return true;   // cycle
                }
            }
        }
        return false;
    }

    public static boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj){

        boolean visited[] = new boolean[V];

        for(int i=0;i<V;i++){
            if(!visited[i]){
                if(bfs(i, V, adj, visited)) return true;
            }
        }
        return false;
    }


    // ================= DRIVER =================
    public static void main(String args[]){

        int V = 5;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

        for(int i=0;i<V;i++) adj.add(new ArrayList<>());

        // Undirected graph
        adj.get(0).add(1);
        adj.get(1).add(0);

        adj.get(1).add(2);
        adj.get(2).add(1);

        adj.get(2).add(3);
        adj.get(3).add(2);

        adj.get(3).add(1);
        adj.get(1).add(3);

        adj.get(3).add(4);
        adj.get(4).add(3);

        System.out.printf(isCycle(V, adj) ? "Cycle detected\n" : "No cycle detected\n");
    }
}