Cycle Detection Pattern
What is Cycle Detection?
Cycle detection is a pattern that uses DFS to find cycles (loops) in a graph. A cycle is a path that starts and ends at the same vertex, with at least one edge.
This pattern is useful in many applications, such as detecting deadlocks in systems, finding circular dependencies, and checking if a graph is a tree or DAG.
Directed vs. Undirected Graphs
The approach to cycle detection differs slightly between directed and undirected graphs:
- Directed Graphs: Use a recursion stack to keep track of vertices in the current DFS path
- Undirected Graphs: Keep track of the parent vertex to avoid false cycles due to bidirectional edges
Cycle Detection in Directed Graphs
Here's an implementation of cycle detection in a directed graph:
Cycle Detection in Undirected Graphs
Here's an implementation of cycle detection in an undirected graph:
Time and Space Complexity
Time Complexity:
O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity:
O(V), where V is the number of vertices in the graph, for storing the visited set and recursion stack.
Application: Course Schedule
A common application of cycle detection is the Course Schedule problem, where we need to determine if it's possible to finish all courses given their prerequisites.
Pattern 2: Cycle Detection
Learn how to use DFS to detect cycles in a graph by keeping track of vertices in the current recursion stack.
What is Cycle Detection?
Cycle detection is a pattern that uses DFS to find cycles (loops) in a graph. A cycle is a path that starts and ends at the same vertex, with at least one edge.
This pattern is useful in many applications, such as detecting deadlocks in systems, finding circular dependencies, and checking if a graph is a tree or DAG (Directed Acyclic Graph).
Key Insight: The key to detecting cycles with DFS is to keep track of vertices that are currently being explored (in the recursion stack). If we encounter a vertex that is already in the recursion stack, we've found a cycle.
Directed vs. Undirected Graphs
Directed Graphs
In a directed graph, a cycle is a path that follows the direction of edges and returns to the starting vertex. We use a recursion stack to keep track of vertices in the current DFS path.
Example: A → B → C → A is a cycle in a directed graph.
Undirected Graphs
In an undirected graph, a cycle is a path that returns to the starting vertex without using the same edge twice. We need to keep track of the parent vertex to avoid false cycles due to bidirectional edges.
Example: A — B — C — A is a cycle in an undirected graph.
The Cycle Detection Approach
1Initialize
Initialize a visited set and a recursion stack (for directed graphs) or a parent tracker (for undirected graphs).
2Start DFS
For each unvisited vertex, start DFS from it. This handles disconnected graphs.
3Track Path
For directed graphs, add the current vertex to the recursion stack. For undirected graphs, keep track of the parent vertex.
4Check Cycles
For directed graphs, if a neighbor is in the recursion stack, a cycle is found. For undirected graphs, if a neighbor is visited and not the parent, a cycle is found.
Cycle Detection in Directed Graphs
Here's an implementation of cycle detection in a directed graph:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657function hasCycle(graph) { // Set to keep track of visited vertices const visited = new Set(); // Set to keep track of vertices in the current recursion stack const recursionStack = new Set(); // Check each vertex as a possible starting point for (const vertex in graph) { if (dfsHasCycle(graph, vertex, visited, recursionStack)) { return true; } } // No cycle found return false;} function dfsHasCycle(graph, vertex, visited, recursionStack) { // If the vertex is not visited yet if (!visited.has(vertex)) { // Mark the vertex as visited visited.add(vertex); // Add the vertex to the recursion stack recursionStack.add(vertex); // Visit all the neighbors for (const neighbor of graph[vertex]) { // If the neighbor is not visited and a cycle is found in the subtree if (!visited.has(neighbor) && dfsHasCycle(graph, neighbor, visited, recursionStack)) { return true; } // If the neighbor is in the recursion stack, a cycle is found else if (recursionStack.has(neighbor)) { return true; } } } // Remove the vertex from the recursion stack recursionStack.delete(vertex); // No cycle found in this subtree return false;} // Example usage:const directedGraph = { 'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': ['E'], 'E': ['A'] // This edge creates a cycle: A -> B -> D -> E -> A}; console.log(hasCycle(directedGraph)); // Output: trueHow it works: We use a recursion stack to keep track of vertices in the current DFS path. If we encounter a vertex that is already in the recursion stack, we've found a cycle. After exploring all neighbors of a vertex, we remove it from the recursion stack.
Cycle Detection in Undirected Graphs
Here's an implementation of cycle detection in an undirected graph:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849function hasCycleUndirected(graph) { // Set to keep track of visited vertices const visited = new Set(); // Check each vertex as a possible starting point for (const vertex in graph) { if (!visited.has(vertex) && dfsHasCycleUndirected(graph, vertex, visited, null)) { return true; } } // No cycle found return false;} function dfsHasCycleUndirected(graph, vertex, visited, parent) { // Mark the vertex as visited visited.add(vertex); // Visit all the neighbors for (const neighbor of graph[vertex]) { // If the neighbor is not visited if (!visited.has(neighbor)) { // Recursively check if there's a cycle in the subtree if (dfsHasCycleUndirected(graph, neighbor, visited, vertex)) { return true; } } // If the neighbor is visited and not the parent, a cycle is found else if (neighbor !== parent) { return true; } } // No cycle found in this subtree return false;} // Example usage:const undirectedGraph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B', 'E'], // This edge creates a cycle: B -> D -> E -> B 'E': ['B', 'D'], 'F': ['C']}; console.log(hasCycleUndirected(undirectedGraph)); // Output: trueHow it works: We keep track of the parent vertex to avoid false cycles due to bidirectional edges. If we encounter a vertex that is already visited and not the parent of the current vertex, we've found a cycle.
Time and Space Complexity
Time Complexity
O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Explanation: We visit each vertex once (O(V)) and explore each edge once (O(E)). Even though we run DFS multiple times, each vertex and edge is processed exactly once across all DFS calls.
Space Complexity
O(V), where V is the number of vertices in the graph.
Explanation: We need to store the visited set (O(V)) and the recursion stack (O(V) in the worst case). Overall, the space complexity is O(V).
Applications and Variations
Deadlock Detection
Detecting deadlocks in operating systems, where processes are waiting for resources held by other processes, forming a cycle.
Circular Dependencies
Finding circular dependencies in software modules, package managers, or build systems.
Checking if a Graph is a Tree
An undirected graph is a tree if and only if it is connected and has no cycles.
Application: Course Schedule
A common application of cycle detection is the Course Schedule problem, where we need to determine if it's possible to finish all courses given their prerequisites. If there's a cycle in the prerequisite graph, it's impossible to finish all courses.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152function canFinish(numCourses, prerequisites) { // Build the adjacency list representation of the graph const graph = Array(numCourses).fill().map(() => []); for (const [course, prereq] of prerequisites) { graph[prereq].push(course); } // 0 = not visited, 1 = visiting (in recursion stack), 2 = visited const visited = Array(numCourses).fill(0); // Check for cycles using DFS for (let i = 0; i < numCourses; i++) { if (visited[i] === 0 && hasCycle(graph, i, visited)) { return false; } } // No cycle found, all courses can be finished return true;} function hasCycle(graph, vertex, visited) { // Mark the vertex as visiting visited[vertex] = 1; // Visit all neighbors for (const neighbor of graph[vertex]) { // If the neighbor is not visited, check if there's a cycle in the subtree if (visited[neighbor] === 0) { if (hasCycle(graph, neighbor, visited)) { return true; } } // If the neighbor is in the recursion stack, a cycle is found else if (visited[neighbor] === 1) { return true; } } // Mark the vertex as visited visited[vertex] = 2; // No cycle found in this subtree return false;} // Example usage:const numCourses = 4;const prerequisites = [[1, 0], [2, 1], [3, 2], [0, 3]]; // This creates a cycle: 0 -> 1 -> 2 -> 3 -> 0 console.log(canFinish(numCourses, prerequisites)); // Output: falseHow it works: We build a directed graph where an edge from course A to course B means B is a prerequisite for A. Then we check if there's a cycle in the graph. If there is, it means there's a circular dependency among courses, making it impossible to finish all of them.