Write an algorithm to detect cycles in a directed graph.
- User
Write an algorithm to detect cycles in a directed graph.
Assistant
Examining Cycle Detection
I'm currently focused on the fundamental goal: identifying cycles within a directed graph. The core concept is clear – recognizing paths that loop back to their origin. I'm visualizing the potential traversal methods now, considering the need to efficiently track visited nodes to avoid infinite loops and properly identify the cycles.
Implementing DFS Logic
I'm now detailing the implementation specifics. Using DFS, I plan to track the state of each node, marking it as unvisited, visiting, or visited. A cycle is confirmed when revisiting a node currently in the visiting state. I'm focusing on the recursion's mechanics, ensuring proper stack management for effective cycle detection.
Formulating DFS Algorithm
The algorithm is taking shape. I'm focusing on the implementation details of DFS, specifically the use of the "gray" state to detect back edges and thus, cycles. Considering the stack-based nature, I'll need to clearly show how the
recursionStackis maintained and how returning TRUE signals cycle discovery. I am also considering edge cases like disconnected graphs and how to handle them.Defining Algorithm Components
I'm now structuring the pseudocode. I've decided to use a
visitedarray to optimize, noting fully processed subtrees, andrecursionStackto track the current path, critical for cycle detection. Refining the logic, I now need to distinguish between nodes visited in past calls versus the current traversal.Outlining DFS Implementation
I'm now structuring the outline. The concept of back edges, which trigger cycle detection, are core to the solution. I'm focusing on crafting the pseudocode, detailing the
recursionStack's purpose, and including thevisitedarray to optimize for processing disconnected segments. I'm also planning the presentation, adding Python code and complexity analysis.Detailing Python Implementation
I'm now writing Python code, focusing on clarity. A function receiving the adjacency list is simpler for demonstration. I'm prioritizing the recursive helper function for cycle detection, detailing how the recursion stack identifies back edges. Edge cases, like disconnected graphs, and self-loops are now checked to ensure correctness. I plan to include concise complexity analysis after the code block.
The most efficient and common way to detect a cycle in a directed graph is using Depth First Search (DFS).
The Core Concept: "The Back Edge"
In a directed graph, a cycle exists if, during a traversal, we encounter an edge leading from the current node to a node that is currently in the recursion stack (an ancestor). This type of edge is called a "Back Edge".
To track this, we need to keep track of the state of each node. A node can be in one of three states:
- Unvisited: We haven't touched this node yet.
- Visiting (Recursion Stack): We are currently processing this node or its descendants.
- Visited: We have finished processing this node and all of its descendants.
If we encounter a node marked as "Visiting", we have found a cycle.
The Algorithm (Pseudocode)
Input: Graph represented as an adjacency list.
- Initialize two arrays (or sets) of size :
visited: To track nodes that have been completely processed.recStack: To track nodes currently in the traversal path.
- Iterate through every node from to (to handle disconnected graphs):
- If node is not
visited:- Call the recursive DFS function
isCyclic(i, visited, recStack). - If the function returns
True, a cycle exists.
- Call the recursive DFS function
- If node is not
- If the loop finishes without returning
True, the graph has no cycles.
Recursive Function
isCyclic(u, visited, recStack):- Mark
visited[u]=True. - Mark
recStack[u]=True. - For each neighbor of :
- If is not
visited:- Recursively call
isCyclic(v). If it returnsTrue, returnTrue.
- Recursively call
- Else If
recStack[v]isTrue:- Cycle Detected! Return
True.
- Cycle Detected! Return
- If is not
- Remove from
recStack(backtracking step). - Return
False.
Python Implementation
Here is a clean implementation using an Adjacency List.
def has_cycle(num_nodes, edges): # 1. Build Adjacency List graph = [[] for _ in range(num_nodes)] for u, v in edges: graph[u].append(v) # Arrays to track state visited = [False] * num_nodes rec_stack = [False] * num_nodes # DFS Recursive Helper def dfs(node): # Mark current node as visited and part of current recursion stack visited[node] = True rec_stack[node] = True # Check all neighbors for neighbor in graph[node]: # If neighbor is not visited, traverse it if not visited[neighbor]: if dfs(neighbor): return True # If neighbor is currently in the recursion stack, we found a cycle elif rec_stack[neighbor]: return True # Backtracking: Remove node from recursion stack before returning rec_stack[node] = False return False # 2. Iterate over all nodes # (Necessary because the graph might differ into disconnected components) for node in range(num_nodes): if not visited[node]: if dfs(node): return True return False # --- Example Usage --- if __name__ == "__main__": # Graph with a cycle: 0->1, 1->2, 2->0 V = 4 edges_cycle = [(0, 1), (1, 2), (2, 0), (2, 3)] # Graph without a cycle: 0->1, 0->2 edges_no_cycle = [(0, 1), (0, 2)] print("Graph 1 has cycle:", has_cycle(V, edges_cycle)) # Output: True print("Graph 2 has cycle:", has_cycle(3, edges_no_cycle)) # Output: FalseComplexity Analysis
- Time Complexity:
- is the number of vertices, is the number of edges.
- In the worst case, the algorithm visits every node and every edge exactly once.
- Space Complexity:
- We use two auxiliary arrays (
visited,rec_stack) of size . - The recursion stack for the DFS can go up to depth in the worst case (a straight line graph).
- We use two auxiliary arrays (
Alternative: Kahn's Algorithm (BFS)
Another popular way to solve this is using Kahn's Algorithm for Topological Sorting.
- Calculate the in-degree of all nodes.
- Add all nodes with in-degree 0 to a queue.
- Process the queue: Remove a node, decrease the in-degree of its neighbors. If a neighbor's in-degree becomes 0, add it to the queue.
- Count the processed nodes.
- If
count_processed_nodes < total_nodes, there is a cycle (because nodes in a cycle never reach in-degree 0).
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.