Visualizer CodeViz · Algorithms, visualized

Part II · Directed graphs · week 2

Directed cycle detection

An edge to a vertex still on the recursion stack closes a cycle. An edge to a finished vertex does not — that one distinction is the whole algorithm.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

timeO(V + E)
answersis this a DAG?
extra stateon_stack[]
used bytopological sort, build systems

Reference: Sedgewick & Wayne, §4.2.

Directed cycle detection in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class DirectedCycle:
    # marked[v]   : v has been visited at some point
    # on_stack[v] : v is on the CURRENT recursion path
    # An edge to an on-stack vertex is a back edge, hence a cycle.

    def __init__(self, digraph):
        self.marked = [False] * digraph.V
        self.on_stack = [False] * digraph.V
        self.edge_to = [None] * digraph.V
        self.cycle = None
        for v in range(digraph.V):
            if not self.marked[v] and self.cycle is None:
                self._dfs(digraph, v)

    def _dfs(self, digraph, v):
        self.on_stack[v] = True
        self.marked[v] = True
        for w in digraph.adj(v):
            if self.cycle is not None:
                return
            if not self.marked[w]:
                self.edge_to[w] = v
                self._dfs(digraph, w)
            elif self.on_stack[w]:        # BACK EDGE: w is still open
                self.cycle = [w]
                x = v
                while x != w:             # walk edge_to back to w
                    self.cycle.append(x)
                    x = self.edge_to[x]
                self.cycle.append(w)
                self.cycle.reverse()
        self.on_stack[v] = False          # v is finished, not on the path

Why it works

Two arrays, two different questions

marked[v] asks have I ever been to v? — on_stack[v] asks am I still inside the call for v? An edge to a marked-but-finished vertex is harmless: it points into a part of the graph you have already left, so it cannot lead back to you. An edge to an on-stack vertex points at a vertex that is still on your current path, so following the path forward and taking that edge returns you to where you are — a cycle.

Testing marked instead of on_stack is the classic bug: the diamond preset (0→1→3, 0→2→3) has no cycle, but reaches 3 twice.

Recovering the cycle itself

Detecting a cycle is not enough for a useful error message; you want to print it. edge_to[] holds the current path, so walking back from v until you reach w collects the cycle in reverse. That is exactly what a build tool does when it reports “circular dependency: A → B → C → A”.

Why anyone cares

A digraph without a cycle (a DAG) can be scheduled; one with a cycle cannot. That makes this the check behind make, package managers, course prerequisites, spreadsheet formula evaluation and deadlock detection — and it is the precondition topological sort quietly relies on.

Undirected graphs differ

In an undirected graph every edge looks like a back edge from the other end, so you must ignore the edge you arrived on — and any other repeat encounter is a genuine cycle. The two cases are not the same code, which is why the course treats digraphs separately.

What to try in the animation

Every edge is directed. The default has one cycle, 1→2→3→1; the tinyDAG preset has none.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Directed cycle detection in the player →

The rest of Directed graphs