Cycle Detection
Detecting cycles in a graph is crucial for many algorithms. Methods differ for directed and undirected graphs.
Cycle Detection in Undirected Graph (using DFS)
During DFS, if a neighbor is visited and is not the parent, a cycle exists.
private boolean hasCycleUndirected(int u, int parent, boolean[] visited) {
visited[u] = true;
for (int v : adjList[u]) {
if (!visited[v]) {
if (hasCycleUndirected(v, u, visited)) return true;
} else if (v != parent) {
return true;
}
}
return false;
}
Cycle Detection in Directed Graph (using DFS with recursion stack)
Track nodes in current recursion stack. If a neighbor is in the stack, cycle exists.
private boolean hasCycleDirected(int u, boolean[] visited, boolean[] recStack) {
visited[u] = true;
recStack[u] = true;
for (int v : adjList[u]) {
if (!visited[v]) {
if (hasCycleDirected(v, visited, recStack)) return true;
} else if (recStack[v]) {
return true;
}
}
recStack[u] = false;
return false;
}
Two Minute Drill
- Undirected: during DFS, if neighbor visited and not parent → cycle.
- Directed: use recursion stack to track current path.
- Time O(V+E), space O(V).
- Cycle detection essential for topological sort and many algorithms.
Need more clarification?
Drop us an email at career@quipoinfotech.com