Topological Sort

Before a compiler can build your program it must sort the source files. Before a course scheduler can enroll you in Advanced Algorithms it must check you've passed Discrete Math. Before npm installs a package it must install that package's own dependencies first. All three problems share a single shape: put things in an order where every prerequisite comes before the thing that needs it.

The mathematical object behind this shape is a directed acyclic graph (DAG) — dots connected by arrows, with no way to follow arrows in a circle back to where you started. Each dot is a task; each arrow says "this must come before that." A topological ordering is any sequence of the dots where every arrow points only forward.

The remarkable fact is that such an ordering can always be found in linear time — $O(V + E)$, where V is the number of tasks and E the number of dependencies. No backtracking, no guessing, no exponential blowup. The only obstacle is a cycle: if task A depends on B which depends on A, no valid order exists, and the algorithm detects this immediately.

Two classic algorithms find topological orders: Kahn's algorithm (1962), which repeatedly plucks tasks with no remaining prerequisites, and depth-first search (DFS) post-order reversal, which was noted by Knuth and later taught in every algorithms textbook. Both run in $O(V + E)$ time.

Build your own dependency graph below. Add tasks (nodes) and dependencies (directed edges), then click Sort to run Kahn's algorithm and watch a valid ordering appear. Introduce a cycle and the algorithm will catch it.

<div class="hint">{{hint}}</div>
<div class="controls">
  <div class="row">
    <input id="nodeName" type="text" placeholder="{{placeholder_node}}" maxlength="12" />
    <button id="addNode" type="button">{{btn_add_node}}</button>
  </div>
  <div class="row">
    <select id="edgeFrom"></select>
    <span class="arrow-label">→</span>
    <select id="edgeTo"></select>
    <button id="addEdge" type="button">{{btn_add_edge}}</button>
  </div>
  <div class="row">
    <button id="sortBtn" type="button" class="primary">{{btn_sort}}</button>
    <button id="stepBtn" type="button">{{btn_step}}</button>
    <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
    <button id="exampleBtn" type="button" class="ghost">{{btn_load_example}}</button>
  </div>
</div>
<canvas id="canvas" width="560" height="220"></canvas>
<div class="result" id="result">{{result_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.4; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .5rem; }
.row { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; }
input, select { font: 14px system-ui, sans-serif; padding: .3rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; background: #fff; }
input { width: 130px; }
select { max-width: 110px; }
.arrow-label { font-weight: 700; color: #1d3557; }
button { font: 600 13px system-ui, sans-serif; padding: .3rem .75rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.primary { background: #2a7ac5; border-color: #2a7ac5; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; width: 100%; border: 1px solid #cdd9e3; border-radius: 8px; background: #f8fafc; }
.result { font-size: .9rem; font-weight: 600; margin-top: .5rem; min-height: 1.5em; padding: .4rem .6rem; border-radius: 6px; background: #e8eef3; color: #1d3557; white-space: pre-wrap; }
.result.ok { background: #d4edda; color: #155724; }
.result.err { background: #f8d7da; color: #721c24; }
.result.step { background: #fff3cd; color: #856404; }

// Code not found

Notice that each step of Kahn's algorithm picks any node whose in-degree (number of unsatisfied prerequisites) has reached zero. Multiple valid orderings often exist — any is acceptable as long as every arrow points forward. The moment a cycle is present, some nodes never reach in-degree zero, and the algorithm reports the cycle rather than an ordering.

Topological sort is a solved problem in the best possible sense: an optimal algorithm has been known since 1962, and the problem sits firmly in P — polynomial time — in fact in linear time.

• Time: $O(V + E)$. Every node is enqueued exactly once; every edge is examined exactly once. There is no smarter algorithm in the worst case because you must at minimum read every edge to know the dependency structure.
• Space: $O(V + E)$. You need to store the graph and an in-degree counter per node.
• Cycle detection is free. At the end of Kahn's algorithm, if any node was never dequeued its in-degree never reached zero, which means it is part of a cycle. No extra pass is needed.
• Not unique. There are often many valid orderings; if you want the lexicographically smallest, replace the queue with a min-heap (O((V + E) log V)).
• Contrast with related hard problems. Finding a Hamiltonian path — visiting every node exactly once — is NP-complete. The difference is that a Hamiltonian path has no given direction constraints; any permutation might work or fail. Topological sort has the direction constraints built in, and that structure makes it easy.

Because topological sort is in P, it is never the bottleneck. Any algorithm that runs a topological sort as a subroutine inherits only the $O(V + E)$ overhead, and this subroutine is used liberally across the whole of computer science.

Topological sort is one of those algorithms that quietly runs inside almost every piece of software infrastructure:

• Build systems (Make, Ninja, Bazel, Gradle): a source file must be compiled before any file that includes it. The build graph is a DAG; topological sort gives the correct compilation order and — crucially — exposes which files can be compiled in parallel (those at the same depth).
• Package managers (npm, pip, apt, Cargo): installing package A first requires installing A's dependencies. Circular dependencies are a package-manager error; the resolver reports them via cycle detection.
• Course planning: universities generate valid course sequences by topologically sorting a prerequisite graph. The same idea applies to project management task sequencing.
• Spreadsheet recalculation: when you change a cell, the spreadsheet engine topologically sorts the dependency graph of formulas and recomputes them in order — updating only what changed, in the right order, with no wasted work.
• Data pipeline scheduling (Airflow, Luigi, dbt): each pipeline stage depends on upstream stages completing first. Topological sort defines the execution schedule, and the DAG view you see in pipeline UIs is literally the same structure.
• Compiler internals: instruction scheduling, register allocation, and dead-code elimination all exploit topological orderings of control-flow and data-flow graphs.

The common thread is "there is a known partial order; I need a total order consistent with it." Topological sort solves exactly that, in the least time possible. See also shortest paths, where DAG shortest paths are solved optimally by processing nodes in topological order.

Topological sort is one of the most satisfying algorithms in all of computer science: the problem has an obvious structure, the algorithm is elegant, and the complexity is optimal. Feed it a DAG and it returns a valid ordering in linear time. Feed it a cycle and it tells you immediately — no valid ordering exists.

The broader lesson is that structure makes problems easy. The directed-acyclic structure of a dependency graph is exactly the gift that turns an otherwise combinatorial search into a single linear pass. Every time you encounter a problem that feels like "there must be a right order," ask whether the constraints form a DAG — if they do, topological sort hands you the answer in $O(V + E)$. If they don't, you may be looking at something far harder, like P vs NP.