Skip to content
TheChatArchiveThe Chat Archive
Grok 4.1 Fast· xaiHugging Face Frontier Reasoning Traces

Write an algorithm to detect cycles in a directed graph.

  1. User

    Write an algorithm to detect cycles in a directed graph.

  2. 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: False
    

    Explanation

    1. Initialization: Assign white (0) to all nodes.
    2. DFS Traversal:
      • Mark node gray on entry.
      • For each neighbor:
        • If gray → Cycle! (back edge).
        • If white → Recurse.
      • Mark black on exit.
    3. 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).

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.