Cycle detection in a graph is one of the applications of depth-first traversal algorithm. Cycle detection in a directed and undirected graph are two different problems (and both can be solved by tweaking DFS). Cycle in a directed graph can be detected through topological sort, which I have already covered here. In this post, I will be covering cycle detection in an undirected graph using DFS traversal.
Tree edge vs Back edge
If you traversing an undirected graph using DFS, each edge can be classified either as tree edge or back edge. This classification helps in identifying if a cycle exists in the graph.
If an undirected graph is implemented though Adjacency List, then edge between vertex u and v i.e. E(u,v) will have two entries. Recall that, method, addEdge(..) is called twice during construction of graph, ref (check out the main method).
graph.addEdge(u,v); //edge from u to v
graph.addEdge(v,u) // edge from v to u
So this means, there are two options to process edge E(u,v) ( as E(u,v) and E(v,u) both mean the same edge); first time when you are exploring vertex u and second time when you exploring vertex v. Edge can be classified as tree edge or back edge when the edge is explored for the first time (i.e. either you start with u or v) . When you encounter edge from vertex u and vertex v is untraversed or undiscovered then edge, E(u,v) becomes tree edge. Discovery of back edge is bit tricky, though. From below example take the case of an edge between 5 and 2 i.e. E(5,2). So when you start exploring this edge from vertex 5, vertex 2 is already explored and it's not the parent of vertex 5. So edge, E(5,2) becomes a tree edge as shown in below diagram.
 |
| Edge classification: referred from 'Algorithm Design Manual' book |
Back edges, help in finding cycle in undirected graph. If there are no back edges, then all edges are tree edge and hence no cycle exists in the graph. But presence of any back-edge confirms the presence of cycle.
Implementation
I have tweaked DFS implementation to return back edges. Below is code with the main method as a test method. Method, traverse(..) processes adjacent nodes/vertices from a source vertex to confirm if it's back-edge.
package graph.algo;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
/**
* Detect loop in an undirected graph using DFS
*
* @author Siddheshwar
*
* @param <V>
*/
public class DetectCycle<V> {
private Graph<V> graph; // graph on which dfs will be performed
private Deque<V> stack; // Deque used to implement stack
private Set<V> visited; // stores set of visited nodes
public DetectCycle(Graph<V> graph) {
this.graph = graph;
stack = new ArrayDeque<>();
visited = new LinkedHashSet<>(); // to maintain the insertion order
}
/**
* Iterative/stack based DFS implementation
*
* @param source
*/
public Map<V, List<V>> traverse(V source) {
Objects.requireNonNull(source);
if (this.graph == null || this.graph.isEmpty()) {
throw new IllegalStateException(
"Valid graph object is required !!!");
}
// map back edges..source to destination
Map<V, List<V>> backEdges = new LinkedHashMap<>();
stack.push(source);
this.markAsVisited(source);
boolean pop = false;
V stackTopVertex;
V parent = null;
//System.out.print(" " + source);
List<V> targetVerticesOfEdge = null;
while (!stack.isEmpty()) {
if (pop == true)
stackTopVertex = stack.pop();
else
stackTopVertex = stack.peek();
List<V> neighbors = graph.getAdjacentVertices(stackTopVertex);
/**
* process neighboring vertex for back edge before continuing with
* DFS
*/
source = stackTopVertex;
for (V dest : neighbors) {
if ((pop != true) && (parent != null) && (dest != parent)
&& (visited.contains(dest))) {
System.out.println("\n (Back Edge :" + source + " , "
+ dest + " )");
if (backEdges.containsKey(source)) {
targetVerticesOfEdge = backEdges.get(source);
targetVerticesOfEdge.add(dest);
} else {
targetVerticesOfEdge = new ArrayList<>();
targetVerticesOfEdge.add(dest);
backEdges.put(source, targetVerticesOfEdge);
}
}
}
parent = stackTopVertex;
if (!neighbors.isEmpty()
&& hasUnvisitedNeighbor(neighbors, visited)) {
for (V a : neighbors) {
if (!this.isVertexVisited(a)) {
//System.out.print(" " + a);
visited.add(a);
stack.push(a);
// break from loop if an unvisited neighbor is found
break;
}
}
} else {
// if all neighbors are visited
pop = true;
}
}
return backEdges;
}
/**
* checks if any of the neighbor is unvisited
*
* @param neighbors
* @param visited
* @return
*/
private boolean hasUnvisitedNeighbor(List<V> neighbors, Set<V> visited) {
for (V i : neighbors) {
if (!visited.contains(i))
return true;
}
return false;
}
private boolean isVertexVisited(V v) {
return this.visited.contains(v);
}
private void markAsVisited(V v) {
this.visited.add(v);
}
// test method
public static void main(String[] args) {
Graph<Integer> graph = new Graph<>();
graph.addEdge(1, 2);
graph.addEdge(1, 5);
graph.addEdge(1, 6);
graph.addEdge(2, 3);
graph.addEdge(2, 5);
graph.addEdge(3, 4);
graph.addEdge(5, 4);
// for undirected graph
graph.addEdge(2, 1);
graph.addEdge(5, 1);
graph.addEdge(6, 1);
graph.addEdge(3, 2);
graph.addEdge(5, 2);
graph.addEdge(4, 3);
graph.addEdge(4, 5);
DetectCycle<Integer> dfs = new DetectCycle<>(graph);
Map<Integer, List<Integer>> backedges = dfs.traverse(1);
System.out.println("\n\n Back Edges Are --" + backedges);
}
}
Output:
(Back Edge: 5, 1 )
(Back Edge: 5, 2 )
Back Edges Are --{5=[1, 2]}
keep coding !!!
