Visualizer CodeViz · Algorithms, visualized

Part II · Directed graphs · week 2

Topological sort

Add each vertex to a list only after everything it points to is finished, then reverse the list. One DFS, and the schedule is correct.

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

Cost and properties

timeO(V + E)
requiresa DAG — no directed cycle
trickreverse postorder, not preorder
used bymake, package managers, spreadsheets

Reference: Sedgewick & Wayne, §4.2.

Topological sort 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 Topological:
    # A vertex joins the postorder only AFTER every vertex it points to is
    # finished. So in the postorder, every vertex appears after all of its
    # successors -- and reversing it puts every vertex BEFORE them.

    def __init__(self, digraph):
        self.marked = [False] * digraph.V
        self.postorder = []
        for v in range(digraph.V):
            if not self.marked[v]:
                self._dfs(digraph, v)
        self.order = list(reversed(self.postorder))

    def _dfs(self, digraph, v):
        self.marked[v] = True
        for w in digraph.adj(v):
            if not self.marked[w]:
                self._dfs(digraph, w)
        self.postorder.append(v)          # AFTER the loop -- v is finished

Why it works

Why reverse postorder

Preorder (adding v when you enter it) is wrong: you can enter v before discovering a long chain that must precede it. Postorder is safe because append(v) runs only after the recursive calls for all of v's successors have returned — so at that moment every vertex v points to is already in the list. In the postorder each vertex therefore follows all of its successors; reverse it and each vertex precedes them, which is precisely a topological order.

One line, easy to get wrong

self.postorder.append(v) is outside the for loop. Move it inside or above and the code still runs, still terminates, and produces an order that is subtly wrong on some inputs — the kind of bug that ships. Step through the frames and watch how late each vertex is appended.

It must be a DAG

With a cycle there is no valid order at all (each vertex in the cycle would have to precede itself), and this code would return a plausible-looking list anyway. Real implementations run cycle detection first and report the cycle if there is one — which is exactly what make or a package manager does.

Kahn's algorithm, for comparison

The other standard method: repeatedly emit a vertex with in-degree 0 and remove its edges (that is how the layered drawing here is computed). Same O(V + E), no recursion, and it detects cycles naturally — if no vertex has in-degree 0 while vertices remain, there is a cycle. The DFS version wins on brevity; Kahn's wins when you want the levels too, since level k is a set of tasks that can run in parallel.

What to try in the animation

Vertices are drawn left to right by longest path from a source, so a correct topological order always reads left to right. Add a cycle and the layering — and the order — breaks.

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 Topological sort in the player →

The rest of Directed graphs