Cycle Detection in Graphs¶

Determining Whether a Path Loops Back¶

After Dijkstra taught us to care about path cost, cycle detection shifts the question back to graph structure: can a path come back to a node that is already on the current route? That matters in dependency graphs, approval workflows, task schedulers, and package managers, where a loop can make progress impossible.

graph_with_cycle = {
    "A": ["B", "C", "D"],
    "B": ["E", "F"],
    "C": ["G"],
    "D": ["H"],
    "E": ["G"],
    "F": [],
    "G": ["B"],
    "H": [],
}

graph_without_cycle = {
    "A": ["B", "C", "D"],
    "B": ["E", "F"],
    "C": ["G"],
    "D": ["H"],
    "E": ["G"],
    "F": [],
    "G": [],
    "H": [],
}

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

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

        visited.add(node)
        path_stack.add(node)

        for neighbor in graph[node]:
            if dfs(neighbor):
                return True

        path_stack.remove(node)
        return False

    return any(dfs(node) for node in graph if node not in visited)

print("Cyclic graph has cycle:", has_cycle(graph_with_cycle))
print("Acyclic graph has cycle:", has_cycle(graph_without_cycle))
print("Cycle-causing branch from B:", graph_with_cycle["B"], "then", graph_with_cycle["E"], "then", graph_with_cycle["G"])

Cyclic graph has cycle: True
Acyclic graph has cycle: False
Cycle-causing branch from B: ['E', 'F'] then ['G'] then ['B']

Core Idea and Visual Intuition¶

Cycle detection asks a structural question: does any directed path return to a node that is still active in the current DFS path? If yes, the graph contains a cycle.

`visited` means

`path_stack` means

Why this matters next

The node was seen sometime earlier in the traversal, so we do not need to solve it again from scratch.

Worked Example and Practice Lab¶

Guided Practice¶

Which situation proves a directed cycle during DFS?¶

A node has two outgoing edgesBranching alone does not create a loop.

A neighbor is already on the current active pathCorrect. Returning to a node still in the active path confirms a cycle.

A node has been visited sometime earlierVisited alone is not enough for the directed-cycle test.

The graph has more than one leafLeaf count does not define a cycle.

Why does `B -> E -> G -> B` count as a cycle?¶

Because `B` has two neighborsThe number of neighbors is not the core issue.

Because the path returns to `B` before the branch is finishedCorrect. That is a loop back into the active path.

Because `G` is a leaf node`G` is not a leaf here; it points back to `B`.

Because the graph is weightedWeights are irrelevant to this notebook.

Why is cycle detection a natural bridge to topological sorting?¶

Because both algorithms require weighted edgesNeither concept depends on weights.

Because topological sorting works best when a cycle existsA cycle actually blocks a valid topological order.

Because topological sorting only works on directed acyclic graphsCorrect. Cycle detection tells you whether a dependency order is possible.

Because both algorithms always start from leaf nodesThat is not the defining link between them.

Exercises¶

Remove the edge G -> B and predict the result before running the code.
Add a new edge H -> C. Decide whether that creates a cycle and explain why.
Modify has_cycle so it returns the first repeated node instead of only True or False.

Key Takeaway¶

Cycle detection is about path state, not path cost. A directed cycle appears when DFS returns to a node that is still active on the current branch. That idea sets up the next notebook naturally: if no cycle exists, we can try to produce a valid topological order.