Topological Sort: Ordering a DAG

Ordering a graph that has "before" and "after"

A directed acyclic graph (DAG) is exactly what it sounds like: edges have a direction, and there are no cycles — no way to follow directed edges and end up back where you started. Whenever the edges of a graph mean "must happen before" — compile this file before that one, finish this course before that one, calculate this spreadsheet cell before that one — a topological order is a full ordering of every node such that every edge points from an earlier node to a later one. It is the formal answer to "in what order can I safely do all of this."

Kahn's algorithm: peel off what has no dependencies left

The most intuitive algorithm (Kahn, 1962) tracks each node's indegree — how many edges point into it, i.e. how many unfinished prerequisites it has. Any node with indegree zero has nothing left blocking it, so it is safe to output next; removing it from the graph then lowers the indegree of everything it pointed to, possibly freeing up more nodes.

kahn(graph):
  indegree[v] = number of incoming edges, for every node v
  queue = all nodes with indegree == 0
  order = []

  while queue not empty:
    u = queue.pop()
    order.append(u)
    for each edge u -> v:
      indegree[v] -= 1
      if indegree[v] == 0:
        queue.push(v)

  if len(order) < total node count:
    return "cycle detected — no topological order exists"
  return order

live demo · peeling zero-indegree nodes off a dependency graph● LIVE

Every node and every edge is visited a constant number of times, so Kahn's algorithm runs in O(V + E). The order it produces is not necessarily unique — any two nodes that never depend on each other, directly or transitively, can appear in either relative order, so a DAG typically admits many valid topological orders.

The DFS alternative: reverse postorder

A second, equally common approach runs a depth-first search from every unvisited node and records each node the moment its DFS call finishes — after all of its descendants have already finished. Reversing that finish-order list gives a valid topological order, because a node cannot finish before any node it points to has already finished (that descendant was necessarily visited, and finished, during the same DFS call). This version is elegant and needs no explicit indegree bookkeeping, but detecting a cycle requires tracking the current recursion stack separately (a "grey" node revisited while still on the stack signals a cycle), whereas Kahn's algorithm gets cycle detection for free as a byproduct of the final count check.

Why cycles break everything

If the graph contains a cycle, no topological order can exist at all: every node in the cycle would need to come both before and after some other node in the same cycle, which is a logical contradiction. This is exactly why the leftover-nodes check in Kahn's algorithm works as cycle detection — nodes trapped inside a cycle always retain at least one incoming edge from within that same cycle and so never reach indegree zero, never get queued, and never make it into the output order.

Where this runs every day

Build systems (Make, Bazel, npm/yarn's task graphs) topologically sort the dependency graph of targets so that every target is built only after everything it depends on. Package managers resolve install order the same way. Course-prerequisite planning, spreadsheet formula evaluation (recalculating cell B2 only after every cell it references has settled), and task schedulers in distributed workflow engines all reduce, structurally, to the same problem: build the DAG of "must happen before" relationships, then run Kahn's algorithm or DFS postorder to find a safe execution order — or discover, from the leftover nodes, that no safe order exists because someone introduced a circular dependency.

Frequently asked questions

Why does a graph need to be a DAG for topological sort to work?

A topological order requires every edge to point from earlier to later in the sequence. If the graph has a cycle, some node in that cycle would have to appear both before and after another node in the cycle, which is impossible. So a valid topological order exists if and only if the graph is a directed acyclic graph — no cycles at all.

Is the topological order of a graph unique?

Usually not. Any two nodes with no path between them, in either direction, can appear in either relative order, so a DAG typically has many valid topological orders. Kahn's algorithm produces a specific one determined by how ties among zero-indegree nodes are broken — using a plain queue gives one valid order, using a priority queue keyed by node ID gives the lexicographically smallest valid order, and so on.

How do build systems use topological sort to detect a circular dependency?

Kahn's algorithm processes nodes by repeatedly removing ones with zero remaining indegree. If the graph has a cycle, every node inside that cycle always has at least one incoming edge from within the cycle, so those nodes are never processed and the algorithm terminates with fewer nodes ordered than the graph actually has. That shortfall is exactly the signal a build system or task scheduler uses to report 'circular dependency detected'.

Try it live

Everything above runs in your browser — open Topological Sort and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Topological Sort simulation