Cycle detection is the problem of determining whether a graph contains a cycle, which is a path where you can start at a vertex and return to it without repeating edges. The approach differs for directed and undirected graphs.
For undirected graphs, we use DFS with parent tracking. A cycle exists if during DFS traversal, we encounter a visited vertex that is not the parent of the current vertex. The algorithm maintains a visited array and passes the parent vertex in recursive calls. Start DFS from any unvisited vertex. For each neighbor of the current vertex, if the neighbor is not visited, recursively visit it. If the neighbor is visited and is not the parent of current vertex, a cycle exists. Time complexity is O of V plus E and space complexity is O of V.
The key insight for undirected graphs is that if we reach an already visited vertex that is not our immediate parent, we must have reached it through a different path, forming a cycle. We need the parent check because in an undirected graph, the edge connecting a node to its parent would otherwise be detected as a cycle.
For directed graphs, we use DFS with recursion stack tracking. A cycle exists if we encounter a vertex that is currently in the recursion stack, meaning we found a back edge. The algorithm maintains two arrays: visited to track all visited vertices, and recursion stack to track vertices in the current DFS path. Start DFS from any unvisited vertex. Mark current vertex as visited and add to recursion stack. For each neighbor, if it is not visited, recursively visit it. If it is in the recursion stack, a cycle exists. After processing all neighbors, remove current vertex from recursion stack. Time complexity is O of V plus E and space complexity is O of V.
The difference is crucial because in directed graphs, visiting an already visited vertex only indicates a cycle if that vertex is in our current path. A vertex visited in a different DFS path does not form a cycle with our current path.
Applications of cycle detection include deadlock detection in operating systems where processes are vertices and resource requests are edges, checking for circular dependencies in build systems or package managers, detecting infinite loops in finite state machines, and verifying if topological sorting is possible which requires a directed acyclic graph.
Example code
// Undirected Graph - DFS with parent tracking
boolean hasCycleUndirected(int v, boolean[] visited, int parent) {
visited[v] = true;
for (int neighbor : adj[v]) {
// If neighbor not visited, recurse
if (!visited[neighbor]) {
if (hasCycleUndirected(neighbor, visited, v))
return true;
}
// If visited and not parent, cycle exists
else if (neighbor != parent) {
return true;
}
}
return false;
}
// Directed Graph - DFS with recursion stack
boolean hasCycleDirected(int v, boolean[] visited, boolean[] recStack) {
visited[v] = true;
recStack[v] = true; // Add to current path
for (int neighbor : adj[v]) {
// If not visited, recurse
if (!visited[neighbor]) {
if (hasCycleDirected(neighbor, visited, recStack))
return true;
}
// If in recursion stack, back edge found
else if (recStack[neighbor]) {
return true;
}
}
recStack[v] = false; // Remove from current path
return false;
}
// Example Undirected:
// 0 - 1 - 2
// | |
// 3 ----- 4
// Cycle: 1-2-4-3-0-1
// Example Directed:
// 0 -> 1 -> 2
// ^ |
// | v
// 4 <------ 3
// Cycle: 0->1->2->3->4->0