Why it matters

Any dependency resolution needs topological sort. Understanding the two algorithms and when to prefer each is core CS.

Advertisement

The architecture

DFS-based: perform DFS; add nodes to output in post-order (after all descendants processed); reverse output.

Kahn's algorithm: repeatedly remove a node with in-degree 0; decrement in-degrees of its neighbors; append to output.

Topological sort methodsDFS-basedpost-order + reverseKahn'sin-degree BFSCycle detectionif some nodes remainMultiple valid orderings usually exist; either algorithm finds one
Two topo sort methods.
Advertisement

How it works end to end

Cycle detection: if not all nodes end up in the output, graph has a cycle. Kahn's detects naturally; DFS needs coloring (white/gray/black).

Multiple valid orderings: any consistent order works. Deterministic tiebreaking gives reproducible results.

Applications: build systems (Make, Ninja), package managers, course scheduling, spreadsheet cell evaluation.