Detect Cycle In An Undirected Graph | Using BFS | Data Structure And Algorithms



Cycle :- In Graph if  your source and destination is same in path is called Cycle of graph
 If You wanna know everything about cycle detection in an undirected graph using bfs then watch given video . this is one of my favourite question .





Full Code Of Detect Cycle In An Undirected Graph | Using BFS :- 

// first create a class Edge 

class Edge{

int source, dest;


public Edge(int src, int dest) {

this.src= src;

this.dest = dest;

}

}


//then Node

class Node {

int v, parent;


Node(int ver, int parent) {

this.ver = ver;

this.parent = parent;

}

}

// then made a graph for adjacency list


import java.util.ArrayList;

import java.util.List;


class Graph {

// A List of Lists to represent an adjacency list

List<List<Integer>> adjList = null;


// Constructor

Graph(List<Edge> edges, int N) {

adjList = new ArrayList<>();


for (int i = 0; i < N; i++) {

adjList.add(new ArrayList<>());

}


// add edges to the undirected graph

for (Edge edge : edges) {

adjList.get(edge.src).add(edge.dest);

adjList.get(edge.dest).add(edge.src);

}

}

}

//make a test class for implementing detect cycle
import java.util.*;

class Test {
// Perform BFS on graph starting from vertex src and
// returns true of cycle is found in the graph
public static boolean BFS(Graph graph, int src, int N) {
// stores vertex is discovered or not
boolean visited[] = new boolean[N];
Queue<Node> q = new ArrayDeque<Node>();
visited[src] = true;
q.add(new Node(src, -1));

while (!q.isEmpty()) {
Node node = q.poll();
for (int u : graph.adjList.get(node.ver)) {
if (!visited[u]) {
visited[u] = true;
q.add(new Node(u, node.ver));
} else if (u != node.parent) {
return true;
}
}
}
return false;
}

// Check if an undirected graph contains cycle or not
public static void main(String[] args) {
// List of graph edges as per above diagram
List<Edge> edges = Arrays.asList(new Edge(1, 2), new Edge(1, 3), new Edge(1, 4), new Edge(2, 5), new Edge(2, 6),
new Edge(5, 9), new Edge(5, 10), new Edge(4, 7), new Edge(4, 8), new Edge(7, 11), new Edge(7, 12),
new Edge(6, 10)
// edge (6->10) has a cycle in the graph
);

// Set number of vertices in the graph
final int N = 15;

// create a graph from edges
Graph graph = new Graph(edges, N);

//  BFS traversal in connected components of graph
if (BFS(graph, 1, N))
System.out.println("Graph contain cycle");
else
System.out.println("Graph doesn't contain any cycle");
}
}