How does depth-first search produce a topological order?

Run DFS over the graph. Each time a vertex finishes — when DFS has fully explored all of its descendants and is about to return — push it onto a list. When DFS is done, reverse that list. The reversed finishing order is a valid topological order, because a vertex always finishes after every vertex it points to.

What is the time complexity of topological sort?

Both the DFS-based method and Kahn's algorithm run in O(V + E) time, where V is the number of vertices and E the number of edges, because each vertex and edge is processed once. Space is O(V) for the recursion stack or queue plus the visited or in-degree bookkeeping.

How does topological sort detect a cycle?

During DFS, mark a vertex 'gray' while it is on the recursion stack and 'black' once it finishes. If DFS ever follows an edge to a gray vertex, that is a back edge — it points to an ancestor still in progress — which means the graph contains a cycle, so no topological order exists. Kahn's algorithm detects the same thing differently: if it cannot output all vertices because some always have a remaining in-degree, those vertices form a cycle.

Where is topological sort used in real life?

Build systems (make, Bazel) deciding compile order, package managers resolving install order, task and job schedulers, spreadsheet cell recalculation, course prerequisite planning, dependency injection wiring, and resolving the order of database migrations — anywhere 'do this before that' constraints must be linearized.

ALGORITHMS · 08 / DFS & TOPOLOGICAL SORT

Build Order.

Q: What is a topological sort?

A topological sort is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge u → v, u comes before v in the ordering. It answers questions like 'in what order can I build these modules so every dependency is ready first?' A topological order exists if and only if the graph has no cycle.

Q: Is the topological order unique?

Usually not. Whenever two vertices have no path between them, they can appear in either relative order, so a single DAG can have many valid topological orders. DFS post-order and Kahn's algorithm may each return a different but equally valid order. The order is unique only when the DAG is a single chain (a Hamiltonian path).

Eight tasks, each waiting on the ones before it. Schedule them by hand and feel the constraints bite — then let a depth-first search dive to the bottom of every dependency and surface a valid build order every time. Then add one bad edge and watch it refuse.

THE GIST · 20 SECONDS

A topological sort lays the vertices of a DAG in a line so every arrow points forward — every task after its prerequisites. The trick: run DFS, and the moment a node finishes (all its descendants explored), push it to a list. Reverse that list and you have a valid order. It runs in O(V + E) — and a cycle is exactly what makes it impossible.

DAGdirected graph, no cycles
In-degreearrows pointing into a node
Finish timewhen DFS leaves a node
Back edgeedge to an in-progress node = cycle

① Order the graph yourself → ② Let DFS reverse its finishes → ③ Add a cycle, watch it refuse

BUILD ORDER

— nothing scheduled yet —

ready to schedule on the stack (visiting) finished / placed in a cycle

An arrow a → b means a must be built before b. DFS dives to the deepest dependency first, so a node only finishes after everything it points to — which is exactly why reversing the finish order gives a legal build order.

UNDER THE HOOD

What you just played, written down

You scheduled it by hand, watched DFS dive and finish nodes bottom-up, then saw a back edge expose a cycle. Here's the same thing as code.

How the Foreman thinks — five steps

Pick any unvisited node. Mark it gray — it's now on the recursion stack.
Recurse into its successors. For each edge out of it, dive into that node first if it hasn't been visited.
Finish the node. Once every successor is done, mark it black and push it onto a list.
Repeat from any node still unvisited, until all are black.
Reverse the list. The reversed finish order is a valid topological order.

WHY REVERSE-POST-ORDER WORKS

For any edge u → v, DFS finishes v before u (it explored v while still inside u). So u sits later in the finish list, and after reversing, u sits earlier — exactly the order topological sort requires. Catch a gray node mid-recursion and you've found a cycle: no order exists.

The algorithm

WHITE, GRAY, BLACK = 0, 1, 2

function topoSort(graph):
    color = {v: WHITE for v in graph}
    order = []                       # finish order
    for s in graph:
        if color[s] == WHITE:
            dfs(s)
    return reversed(order)

function dfs(u):
    color[u] = GRAY                  # on the stack
    for v in neighbours(u):
        if color[v] == GRAY:
            raise CycleError         # back edge!
        if color[v] == WHITE:
            dfs(v)
    color[u] = BLACK
    order.append(u)                  # finished

TIMEO(V + E)every node + edge once

SPACEO(V)colors + recursion stack

Solved by hand — the run for the graph above

DFS finishes nodes deepest-first; reverse that and every arrow points forward.

↔ DFS vs Kahn's algorithm

The DFS way reverses finishing times. Kahn's way is BFS-flavoured: repeatedly emit any node with in-degree 0, then remove its out-edges. Both are O(V + E); Kahn's also surfaces the cycle as "nodes that never reach in-degree 0".

↔ Why a cycle breaks it

In a cycle a → b → … → a, every node waits on another in the loop, so none can go first. A topological order exists iff the graph is acyclic — that's what the D and A in DAG guarantee.

★ Where it's used

Build systems (make, Bazel) picking compile order, package managers, task schedulers, spreadsheet recalculation, course prerequisites, and database migration ordering.

RUN IT YOURSELF

The same algorithm, in Python & TypeScript

Both tabs are the identical algorithm (Kahn's), running for real in your browser — Python through WebAssembly, TypeScript transpiled on the fly. No server. Switch tabs to compare the languages line for line, read the numbered comments, edit anything, and hit Run (or ⌘/Ctrl + Enter). Each language downloads its runtime once on first run.

HOW TO READ THE CODE — 4 IDEAS

in-degree = how many prerequisites a task is still waiting on. The comments mark this step 1.
Any task at in-degree 0 has nothing left to wait for, so it's ready to build now (step 2).
Building a task frees its dependents: drop each of their counters by one; when a counter hits 0, that task becomes ready too (steps 3–5).
If some tasks never reach 0, they're stuck waiting on each other — a cycle, so no order exists (step 6).

CPython · WebAssembly

# A dependency graph: each task maps to the tasks that depend on it.
# An edge  a -> b  means "a must be built before b".
from collections import deque

def topological_sort(graph):
    """Kahn's algorithm. Returns a valid build order, or raises
    ValueError if a cycle makes every order impossible."""

# STEP 1 — count how many prerequisites each task is still
    # waiting on. That count is its "in-degree".
    indeg = {node: 0 for node in graph}
    for node in graph:
        for dependent in graph[node]:
            indeg[dependent] += 1

# STEP 2 — any task with in-degree 0 has nothing to wait for,
    # so it's ready immediately. (sorted() just keeps output stable.)
    ready = deque(sorted(node for node in indeg if indeg[node] == 0))

order = []
    while ready:
        # STEP 3 — pull a ready task and commit it to the build order.
        node = ready.popleft()
        order.append(node)

# STEP 4 — building it frees the tasks that depended on it:
        # each loses one prerequisite.
        for dependent in sorted(graph[node]):
            indeg[dependent] -= 1
            # STEP 5 — that was its last prerequisite? It's ready now.
            if indeg[dependent] == 0:
                ready.append(dependent)

# STEP 6 — if we couldn't place every task, the leftovers are
    # locked in a cycle, so no valid order exists.
    if len(order) != len(indeg):
        raise ValueError("cycle detected - no valid build order")
    return order

# the dependency graph from the lesson above
build = {
    "config": ["db", "api"],
    "utils":  ["api", "ui"],
    "db":     ["auth"],
    "api":    ["auth", "cache"],
    "auth":   ["ui"],
    "cache":  ["deploy"],
    "ui":     ["deploy"],
    "deploy": [],
}

print(" -> ".join(topological_sort(build)))

# Try it: add  "deploy": ["config"]  to make a cycle and watch it raise.

// A dependency graph: each task maps to the tasks that depend on it.
// An edge  a -> b  means "a must be built before b".
type Graph = Record<string, string[]>;

/**
 * Kahn's algorithm. Returns a valid build order, or throws if a
 * cycle makes every order impossible.
 */
function topoSort(graph: Graph): string[] {
  // STEP 1 — count how many prerequisites each task is still
  // waiting on. That count is its "in-degree".
  const indeg: Record<string, number> = {};
  for (const node of Object.keys(graph)) indeg[node] = 0;
  for (const node of Object.keys(graph)) {
    for (const dependent of graph[node]) indeg[dependent]++;
  }

// STEP 2 — any task with in-degree 0 has nothing to wait for,
  // so it's ready immediately. (sort() just keeps output stable.)
  const ready: string[] = Object.keys(indeg)
    .filter((node) => indeg[node] === 0)
    .sort();

const order: string[] = [];
  while (ready.length > 0) {
    // STEP 3 — pull a ready task and commit it to the build order.
    const node = ready.shift()!;
    order.push(node);

// STEP 4 — building it frees the tasks that depended on it:
    // each loses one prerequisite.
    for (const dependent of [...graph[node]].sort()) {
      indeg[dependent]--;
      // STEP 5 — that was its last prerequisite? It's ready now.
      if (indeg[dependent] === 0) ready.push(dependent);
    }
  }

// STEP 6 — if we couldn't place every task, the leftovers are
  // locked in a cycle, so no valid order exists.
  if (order.length !== Object.keys(indeg).length) {
    throw new Error("cycle detected - no valid build order");
  }
  return order;
}

// the dependency graph from the lesson above
const build: Graph = {
  config: ["db", "api"],
  utils:  ["api", "ui"],
  db:     ["auth"],
  api:    ["auth", "cache"],
  auth:   ["ui"],
  cache:  ["deploy"],
  ui:     ["deploy"],
  deploy: [],
};

console.log(topoSort(build).join(" -> "));

// Try it: add  deploy: ["config"]  to make a cycle and watch it throw.

QUICK CHECK

Did it stick?

FAQ

Topological sort, answered

What is a topological sort?

A linear ordering of a DAG's vertices so that for every edge u → v, u comes before v. It linearizes "do this before that" constraints — and exists if and only if the graph has no cycle.

How does DFS produce a topological order?

Run DFS; each time a node finishes (all descendants explored), push it to a list. Reverse the list. Because a node always finishes after everything it points to, the reversed order puts every dependency first.

What is the time complexity?

O(V + E) for both the DFS method and Kahn's algorithm — each vertex and edge is touched once. Space is O(V) for colors plus the recursion stack or the queue.

How does it detect a cycle?

Mark a node gray while it's on the recursion stack, black when it finishes. An edge to a gray node is a back edge — it points to an ancestor still in progress — which means a cycle, so no order exists.

Is the topological order unique?

Usually not. Two nodes with no path between them can go in either order, so most DAGs have many valid orders. It's unique only when the DAG is a single chain.

Where is topological sort used?

Build systems and compilers (compile order), package managers, task schedulers, spreadsheet recalculation, course prerequisites, dependency injection, and ordering database migrations.

Finished this one? 0 / 8 Algorithms done