Graph Patterns: Cycle Detection in Undirected Graphs
In undirected graphs, edges are bidirectional. A simple visited array is not enough to detect a cycle, as a node will always see the neighbor it just came from as 'visited'.
Introduction
In an undirected graph, if Node A is connected to Node B, the adjacency list allows you to travel from A to B, and B back to A immediately.
If we use a simple visited set, Node B will look at Node A, see that it is visited, and falsely declare a cycle.
The Parent Pointer
To solve this, we must carry the parent node along in our DFS or BFS traversal. When inspecting neighbors, if we encounter a visited node, we simply check: Is this node the parent I just came from?
If it is the parent, it's just the reverse edge. We ignore it. But if the neighbor is visited and it is not the parent, it means we have discovered a secondary path to an already explored node. That guarantees a true cycle.
Implementation
class Solution {
public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
boolean[] vis = new boolean[V];
for (int i = 0; i < V; i++) {
if (!vis[i]) {
if (dfs(i, -1, vis, adj)) return true;
}
}
return false;
}
private boolean dfs(int node, int parent, boolean[] vis, ArrayList<ArrayList<Integer>> adj) {
vis[node] = true;
for (int neighbor : adj.get(node)) {
if (!vis[neighbor]) {
if (dfs(neighbor, node, vis, adj)) return true;
}
// If the visited neighbor is NOT the parent we just came from
else if (neighbor != parent) {
return true;
}
}
return false;
}
}