In this post we'll see how to detect a cycle in an undirected graph using depth-first search traversal.
For example, in the following graph 0-2-3-4-0 is a cycle.
Refer post Java Program - Depth First Search (DFS) Traversal For Graph to know in details about DFS 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 - 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.
Refer post Graph Adjacency Representation - Java Program to get better explanation of graph adjacency representation using adjacency matrix or adjacency list.
Program also displays the vertices which are part of the cycle, stack is used to store those vertices.
DFS traversal and the cycle detection logic is in the dfs() method which is called recursively with the adjacent vertex of the current vertex to keep going deep in the current branch. You also keep track of the parent and make a check to ignore such bi-directional connection.
if(v == parent) {
continue;
}
Here is the complete Java program
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
/**
* Undirected graph cycle detection using DFS
*/
public class UndirectedGraphCycle {
private Map<Integer, List<Integer>> adjList;
private int numOfVertices;
private Stack<Integer> stack;
UndirectedGraphCycle(int numOfVertices){
this.numOfVertices = numOfVertices;
adjList = new HashMap<>();
// to keep track of the vertex for the cycle, stack is used
// so that vertices which are visited and not part of the cycle
// can be easily popped
stack = new Stack<>();
}
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();
});
}
public boolean isCycleDetected() {
boolean[] visited = new boolean[numOfVertices];
for(int i = 0; i < numOfVertices; i++) {
if(!visited[i]) {
if(dfs(i, visited, -1)) {
return true;
}
}
}
return false;
}
// Uses DFS traversal (recursive) to detect a cycle
private boolean dfs(int currentVertex, boolean[] visited, int parent) {
visited[currentVertex] = true;
stack.push(currentVertex);
for(int v : adjList.get(currentVertex)) {
System.out.println("Vertex " + v + " Currentv " + currentVertex);
// undirected graph means 2 way connection so
// connection back to parent doesn't mean cycle
if(v == parent) {
continue;
}
// visited array at index is true means that vertex is already visited
// means a cycle
if(visited[v]) {
/*Start - To display the vertices which are part of the cycle */
List<Integer> cycle = new ArrayList<>();
int startIndex = stack.indexOf(v);
for (int i = startIndex; i < stack.size(); i++) {
cycle.add(stack.get(i));
}
// Add the starting node to complete the cycle
cycle.add(v);
System.out.println("Detected cycle is " + cycle);
/*Display logic ends here comment from start to end
* if cycle display not needed*/
return true;
}
// recursive call
if(dfs(v, visited, currentVertex))
return true;
}
// reached here means current vertex is not part of the cycle so pop it
stack.pop();
return false;
}
public static void main(String[] args) {
UndirectedGraphCycle graph = new UndirectedGraphCycle(5);
graph.addEdge(0, 1); //A-B
//graph.addEdge(1, 2); //A-C
graph.addEdge(0, 2); //A-C
graph.addEdge(0, 4); //A-E
graph.addEdge(2, 3); //C-D
graph.addEdge(3, 4); //D-E
graph.printGraph();
if(graph.isCycleDetected()) {
System.out.println("Cycle detected in the graph");
}else {
System.out.println("No Cycle detected 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 Detected cycle is [0, 2, 3, 4, 0] Cycle detected in the graph
Time and space complexity of cycle detection in an undirected graph
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 space for storing adjacency list is 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 DFS - 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