Topological Sort

Kahn's algorithm for ordering dependencies in a DAG

Turn a partial order into a valid sequence

In a directed dependency graph, edge u -> v means that u must appear before v. A topological order satisfies every such edge. It exists only when the graph is acyclic.

Remove vertices with no remaining prerequisite

Kahn's algorithm counts every vertex's indegree. Any vertex with indegree 0 is ready to output. Removing it deletes its outgoing edges, which may reduce another vertex to indegree 0. The player shows indegrees as node badges, the active ready vertex in amber, and completed vertices in green.

Count the incoming edges of every vertex.

1function topoSort(edges: [number, number][], n: number): number[] {
const indeg = Array(n).fill(0);
for (const [u, v] of edges) indeg[v]++;
const order: number[] = [];
const done = Array(n).fill(false);
while (order.length < n) {
  let u = -1;
  for (let i = 0; i < n; i++)
    if (!done[i] && indeg[i] === 0) { u = i; break; }
  if (u === -1) break;
  done[u] = true;
  order.push(u);
  for (const [a, b] of edges) if (a === u) indeg[b]--;
}
return order;
16}

Current vertex-

Output-

Remaining6

indegree[A]1

indegree[B]2

indegree[C]0

indegree[D]1

indegree[E]0

indegree[F]3

1 / 14

Cycles and non-unique answers

Several vertices may be ready at once, so a DAG can have many valid orders. This demonstration chooses the lowest-index ready vertex for a deterministic trace. If vertices remain but none has indegree 0, those dependencies contain a directed cycle. Processing each vertex and edge once takes O(V + E) time.

Typical uses include build scheduling, course prerequisites, spreadsheet recalculation, and detecting circular dependencies.

Continue the graph path with Dijkstra's shortest-path invariant.

Algorithm Visualizer

Topological Sort

Turn a partial order into a valid sequence

Remove vertices with no remaining prerequisite

Cycles and non-unique answers