pythonadvanced15 minutes

Fix Bug in Complex Recursive Depth-First Search Algorithm for Graph Cycle Detection

Identify and correct the logical errors in a recursive depth-first search (DFS) implementation designed to detect cycles in a directed graph. The provided code attempts to return True if a cycle exists, but it fails in some cases. Your task is to debug and fix the code while preserving its overall structure and efficiency.

Challenge prompt

You are provided with a Python function 'has_cycle' that implements a recursive DFS to detect cycles in a directed graph represented as an adjacency list. The function should return True if the graph contains at least one cycle, and False otherwise. However, some test cases reveal it returns incorrect results. Review the code, identify the bugs, and fix them so that cycle detection works correctly for any directed graph input.

Guidance

• Understand how DFS with recursion stack tracking is used to detect cycles in directed graphs.
• Check how nodes are marked as visited and how the recursion stack is updated and cleared.
• Make sure the function returns appropriately once a cycle is detected to avoid unnecessary traversals.
• Test on simple graphs with cycles and without cycles to verify correctness.

Hints

• Pay close attention to how the recursion stack is managed—nodes must be removed after exploring all their neighbors.
• Be cautious about when and where the function returns True when a cycle is found to prevent premature termination.
• Consider whether the 'visited' and 'recStack' data structures are being used consistently throughout the recursion.

Starter code

def has_cycle(graph):
    visited = set()
    recStack = set()

    def dfs(node):
        if node in recStack:
            return True
        if node in visited:
            return False

        visited.add(node)
        recStack.add(node)

        for neighbour in graph.get(node, []):
            dfs(neighbour)

        recStack.remove(node)
        return False

    for vertex in graph:
        if dfs(vertex):
            return True
    return False

Expected output

has_cycle({'A': ['B'], 'B': ['C'], 'C': ['A']}) -> True has_cycle({'A': ['B'], 'B': ['C'], 'C': []}) -> False

Core concepts

graph theorydepth-first searchrecursioncycle detection

Challenge a Friend

Send this duel to someone else and see if they can solve it.