In the post Detect Cycle in an Undirected Graph Using DFS - Java Program we saw how to detect a cycle in an undirected graph using DFS, in this tutorial we'll see how to write a Java program to detect a cycle in an undirected graph using breadth-first search traversal.
For example, in the following graph 0-2-3-4-0 is a cycle.
Refer post Java Program - Breadth First Search (BFS) Traversal For Graph to know in details about breadt-first search traversal of a graph.
Detecting a cycle in an undirected graph
Logic for detecting a graph with graph traversal is simple. If the vertex currently visited has already been visited that means there is a cycle in the graph.
With undirected graph, you also have to consider the fact that the connection between vertices is considered bi-directional. Edge between A and B also means an edge between B and A. This bi-directional connection should not be considered a cycle. For this reason, you also need to keep track of the parent vertex of the current vertex. When list of the adjacent vertices for the current vertex is iterated, connection back to the parent vertex should be ignored.
Cycle detection in an undirected graph using BFS - Java Program
In the Java program adjacency list is used to represent the graph. There is a visited array to keep track of the vertices which are already visited.
Program also displays the vertices which are part of the cycle, a HashMap is used to store the vertices that are part of the cycle.
BFS traversal and the cycle detection logic is in the bfs() method which uses a queue to store the adjacent vertices. You also need to keep track of the parent therefore queue adds the vertex and its parent vertex both as an array.
Queue<int[]> queue = new LinkedList<>();
While traversing the graph using breadth-first search, if you come across a vertex that is already visited but not the parent of the current vertex that means there is a cycle.
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
public class UndirectedGraphCycleBFS {
private Map<Integer, List<Integer>> adjList;
private int numOfVertices;
UndirectedGraphCycleBFS(int numOfVertices){
this.numOfVertices = numOfVertices;
adjList = new HashMap<>();
}
// Creating adjacency list
public void addEdge(Integer source, Integer destination) {
adjList.computeIfAbsent(source, k->new ArrayList<>()).add(destination);
// For undirected graph
adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(source);
}
public void printGraph() {
adjList.forEach((k, v) -> {
System.out.print("Vertex " + k + " Connectes to ");
v.forEach(e -> System.out.print(e + " "));
System.out.println();
});
}
/*Cycle detection logic starts here */
public boolean isCycleDetected() {
boolean[] visited = new boolean[numOfVertices];
for(int i = 0; i < numOfVertices; i++) {
if(!visited[i]) {
if(bfs(i, visited)) {
return true;
}
}
}
return false;
}
private boolean bfs(int currentVertex, boolean[] visited) {
// Queue needs to add parent info for the current vertex
Queue<int[]> queue = new LinkedList<>();
// For starting vertex parent is -1
queue.add(new int[]{currentVertex, -1});
visited[currentVertex] = true;
// This map is used to keep track of the vertices that are part of the cycle
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(currentVertex, -1);
while(!queue.isEmpty()) {
int[] v = queue.poll();
int node = v[0];
int parent = v[1];
for(int n : adjList.get(node)) {
if(!visited[n]) {
visited[n] = true;
queue.add(new int[]{n, node});
map.put(n, node);
}else if(n != parent) { // cycle detected
// display vertices that are part of the cycle
printCycle(map, node, n);
return true;
}
}
}
return false;
}
// Helper method to print the cycle vertices
private void printCycle(Map<Integer, Integer> parentMap, int u, int v) {
List<Integer> cycle = new ArrayList<>();
// Start from the node that caused the cycle detection
cycle.add(v);
int current = u;
while (current != -1 && current != v) {
cycle.add(current);
current = parentMap.get(current);
}
Collections.reverse(cycle); // Reverse to get the cycle in order
cycle.add(parentMap.get(v)); // Add the last vertex
System.out.println("Cycle vertices: " + cycle);
}
public static void main(String[] args) {
UndirectedGraphCycleBFS graph = new UndirectedGraphCycleBFS(10);
// graph.addEdge(0, 1);
// graph.addEdge(0, 2);
// graph.addEdge(0, 3);
// graph.addEdge(0, 7);
// graph.addEdge(1, 4);
// graph.addEdge(4, 5);
// graph.addEdge(2, 5);
// graph.addEdge(3, 6);// Creates a cycle 0-1-4-5-2-0
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);// Creates a cycle [0, 2, 3, 4, 0]
graph.printGraph();
if(graph.isCycleDetected()) {
System.out.println("Cycle found in the graph");
}else {
System.out.println("No cycle found in the graph");
}
}
}
Output
Vertex 0 Connectes to 1 2 4 Vertex 1 Connectes to 0 Vertex 2 Connectes to 0 3 Vertex 3 Connectes to 2 4 Vertex 4 Connectes to 0 3 Cycle vertices: [0, 4, 3, 2] Cycle found in the graph
Time and space complexity of cycle detection in an undirected graph using BFS
With adjacency list only adjacent vertices are stored as a list for each vertex. For each vertex, the DFS algorithm iterates over adjacency list of that vertex. In an adjacency list representation, every edge appears exactly once (directed graph) or twice (undirected graph).
Since the total time = time for vertex processing + time for scanning adjacency list for each vertex = O(V) + O(E) So, the time complexity is O(V + E).
Extra space is needed for visited array which is O(V). In recursive method, call stack may go up to the recursive depth of V in worst case so recursive call space requirement is O(V). Thus, the space complexity can be considered as O(V).
Note that storing adjacency list is also O(V + E) in case you want to include input graph too in the space complexity.
That's all for this topic Detect Cycle in an Undirected Graph Using BFS - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
No comments:
Post a Comment