Grok 4.1 Fast· xai
Frontier Reasoning Traces
Write an algorithm to detect cycles in a directed graph.
- User
Write an algorithm to detect cycles in a directed graph.
- Assistant
# Algorithm: Cycle Detection in a Directed Graph using DFS # # This algorithm uses Depth-First Search (DFS) with color coding to detect cycles: # - White (0): Unvisited # - Gray (1): Being visited (in current recursion stack) # - Black (2): Fully visited # # A cycle exists if we encounter a gray node during DFS (back edge to ancestor). # # Time Complexity: O(V + E), where V is vertices, E is edges # Space Complexity: O(V) for colors and recursion stack # # Input: Graph as adjacency list (dict/list of lists) # Output: True if cycle exists, False otherwise def has_cycle(graph): """ Detects if a directed graph contains a cycle. Args: graph (dict): Adjacency list, e.g., {'A': ['B', 'C'], 'B': ['C'], ...} Returns: bool: True if cycle detected, False otherwise """ colors = {} # Node -> color (0: white, 1: gray, 2: black) def dfs(node): colors[node] = 1 # Mark as gray (visiting) for neighbor in graph.get(node, []): if neighbor not in colors: colors[neighbor] = 0 # Initialize unvisited neighbors if colors[neighbor] == 1: return True # Cycle detected (gray neighbor) if colors[neighbor] == 0 and dfs(neighbor): return True colors[node] = 2 # Mark as black (visited) return False # Initialize all nodes as unvisited for node in graph: colors[node] = 0 # Run DFS from each unvisited node for node in list(colors.keys()): if colors[node] == 0 and dfs(node): return True return False # Example Usage: if __name__ == "__main__": # Graph with cycle: A -> B -> C -> A graph_with_cycle = { 'A': ['B'], 'B': ['C'], 'C': ['A'] } print(has_cycle(graph_with_cycle)) # Output: True # Graph without cycle: A -> B -> C graph_no_cycle = { 'A': ['B'], 'B': ['C'], 'C': [] } print(has_cycle(graph_no_cycle)) # Output: FalseExplanation
- Initialization: Assign white (0) to all nodes.
- DFS Traversal:
- Mark node gray on entry.
- For each neighbor:
- If gray → Cycle! (back edge).
- If white → Recurse.
- Mark black on exit.
- Disconnected Components: Iterate over all nodes to handle forests.
This works for any directed graph, including disconnected ones. For undirected graphs, modify to track parent edges. Alternative: Kahn's BFS with indegrees for topological sort (cycle if not all nodes visited).
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.