AlgoScope

Topological Sort

A directed acyclic graph is a set of tasks with prerequisites, and a topological order is a schedule that respects them. Kahn's algorithm keeps taking a task with no unfinished prerequisites. Depth-first search finishes a task only after everything downstream of it, so its finish order reversed is a schedule too. Either way, a cycle is the one thing that makes a schedule impossible, and both methods notice it.

The player

Topological sort by depth-first search finish order.012345

Depth-first search finishes a vertex only after everything reachable from it is finished. So the finish order lists descendants before ancestors, and reversing it is a topological order. The path shows the vertices currently being explored. An edge back into that path is a cycle.

Check your understanding

The player pauses before each decision in this run and asks what happens next. Here are all 6, with their answers.

  1. At 0, edges to 1, 2. What happens next?

    • Go into 1
    • Go into 2
    • Finish 0

    Answer: Go into 1. 1 has not been seen, so the search dives into it before 0 can finish.

  2. At 1, edges to 3. What happens next?

    • Go into 3
    • Finish 1

    Answer: Go into 3. 3 has not been seen, so the search dives into it before 1 can finish.

  3. At 3, edges to 4. What happens next?

    • Go into 4
    • Finish 3

    Answer: Go into 4. 4 has not been seen, so the search dives into it before 3 can finish.

  4. At 4, edges to nothing. What happens next?

    • Finish 4
    • Keep searching

    Answer: Finish 4. Every neighbour is finished or absent, so 4 is done and goes on the finished list.

  5. At 2, edges to 3, 5. What happens next?

    • Go into 5
    • Finish 2

    Answer: Go into 5. 5 has not been seen, so the search dives into it before 2 can finish.

  6. At 5, edges to nothing. What happens next?

    • Finish 5
    • Keep searching

    Answer: Finish 5. Every neighbour is finished or absent, so 5 is done and goes on the finished list.

How it runs, step by step

  1. Depth-first search finishes a vertex only after everything reachable from it is finished. So the finish order lists descendants before ancestors, and reversing it is a topological order. The path shows the vertices currently being explored. An edge back into that path is a cycle.

    Topological sort by depth-first search finish order.

  2. Enter 0. Its edges go to 1, 2. Unvisited: 1, 2. Go into 1 first.

    Enter vertex 0. Next is 1.

  3. Enter 1. Its edges go to 3. Unvisited: 3. Go into 3 first.

    Enter vertex 1. Next is 3.

  4. Enter 3. Its edges go to 4. Unvisited: 4. Go into 4 first.

    Enter vertex 3. Next is 4.

  5. Enter 4. Its edges go to nothing. Nothing new to explore below it, so 4 will finish.

    Enter vertex 4. It has nothing new below it.

  6. Finish 4 as number 1: everything reachable from it is already finished, so in the final order 4 must come before all of them.

    Vertex 4 finishes as number 1.

  7. Finish 3 as number 2: everything reachable from it is already finished, so in the final order 3 must come before all of them.

    Vertex 3 finishes as number 2.

  8. Finish 1 as number 3: everything reachable from it is already finished, so in the final order 1 must come before all of them.

    Vertex 1 finishes as number 3.

  9. Enter 2. Its edges go to 3, 5. Unvisited: 5. Go into 5 first.

    Enter vertex 2. Next is 5.

  10. Enter 5. Its edges go to nothing. Nothing new to explore below it, so 5 will finish.

    Enter vertex 5. It has nothing new below it.

  11. Finish 5 as number 4: everything reachable from it is already finished, so in the final order 5 must come before all of them.

    Vertex 5 finishes as number 4.

  12. Finish 2 as number 5: everything reachable from it is already finished, so in the final order 2 must come before all of them.

    Vertex 2 finishes as number 5.

  13. Finish 0 as number 6: everything reachable from it is already finished, so in the final order 0 must come before all of them.

    Vertex 0 finishes as number 6.

  14. Finish order 4, 3, 1, 5, 2, 0, reversed: 0, 2, 5, 1, 3, 4. Every edge points from a later finisher to an earlier one, so reversing the finish order sends all edges forward. O(V + E), one DFS.

    The topological order is 0, 2, 5, 1, 3, 4.

The code

Topological Sort, in Python

def kahn(n, adj):
    indegree = [0] * n
    for row in adj:
        for v in row: indegree[v] += 1
    ready = deque([u for u in range(n) if indegree[u] == 0])   # nothing must come before these
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0: ready.append(v)               # its last prerequisite is placed
    return order if len(order) == n else None                  # leftovers mean a cycle

def dfs_order(n, adj):
    state = [0] * n                                            # 0 new, 1 on the path, 2 finished
    finished = []
    def visit(u):
        state[u] = 1
        for v in adj[u]:
            if state[v] == 1: return False                     # back edge: a cycle
            if state[v] == 0 and not visit(v): return False
        state[u] = 2
        finished.append(u)                                     # everything below u is done
        return True
    for u in range(n):
        if state[u] == 0 and not visit(u): return None
    return finished[::-1]                                      # reverse postorder

Topological Sort, in JavaScript

function kahn(n, adj) {
  const indegree = new Array(n).fill(0);
  for (const row of adj) for (const v of row) indegree[v]++;
  const ready = [];
  for (let u = 0; u < n; u++) if (indegree[u] === 0) ready.push(u);   // nothing must come before these
  const order = [];
  while (ready.length > 0) {
    const u = ready.shift();
    order.push(u);
    for (const v of adj[u]) if (--indegree[v] === 0) ready.push(v);   // its last prerequisite is placed
  }
  return order.length === n ? order : null;              // leftovers mean a cycle
}

function dfsOrder(n, adj) {
  const state = new Array(n).fill(0);                    // 0 new, 1 on the path, 2 finished
  const finished = [];
  const visit = (u) => {
    state[u] = 1;
    for (const v of adj[u]) {
      if (state[v] === 1) return false;                  // back edge: a cycle
      if (state[v] === 0 && !visit(v)) return false;
    }
    state[u] = 2;
    finished.push(u);                                    // everything below u is done
    return true;
  };
  for (let u = 0; u < n; u++) if (state[u] === 0 && !visit(u)) return null;
  return [...finished].reverse();                        // reverse postorder
}

Topological Sort, in Kotlin

fun kahn(n: Int, adj: List<List<Int>>): List<Int>? {
    val indegree = IntArray(n)
    adj.forEach { for (v in it) indegree[v]++ }
    val ready = ArrayDeque((0 until n).filter { indegree[it] == 0 })   // nothing must come before these
    val order = mutableListOf<Int>()
    while (ready.isNotEmpty()) {
        val u = ready.removeFirst()
        order += u
        for (v in adj[u]) if (--indegree[v] == 0) ready.addLast(v)   // its last prerequisite is placed
    }
    return if (order.size == n) order else null           // leftovers mean a cycle
}

fun dfsOrder(n: Int, adj: List<List<Int>>): List<Int>? {
    val state = IntArray(n)                                // 0 new, 1 on the path, 2 finished
    val finished = mutableListOf<Int>()
    fun visit(u: Int): Boolean {
        state[u] = 1
        for (v in adj[u]) {
            if (state[v] == 1) return false                  // back edge: a cycle
            if (state[v] == 0 && !visit(v)) return false
        }
        state[u] = 2; finished += u                        // everything below u is done
        return true
    }
    for (u in 0 until n) if (state[u] == 0 && !visit(u)) return null
    return finished.asReversed()                           // reverse postorder
}

This lesson has no write-it-yourself editor. It is free, like every lesson, and nothing here is locked.

Remember

  • Kahn: track in-degrees, place a zero, decrement its neighbours, repeat. Leftovers mean a cycle.
  • DFS: reverse postorder. An edge into a vertex still on the current path is a cycle.
  • Reach for it on dependency ordering and can-everything-finish questions.

Where this is used

Spreadsheet recalculationSpreadsheets

A workbook is a graph where each formula cell has an edge from every cell it reads. Excel and Google Sheets keep that dependency graph and recalculate in topological order, so no cell is ever computed from a stale precedent and one edit only touches what is downstream of it. The circular reference warning is the cycle check firing: there is no order that puts every cell after its inputs, so the engine refuses rather than looping.

systemd boot orderingOperations

Each systemd unit declares Before= and After= relations, which makes a Linux boot a set of jobs with prerequisites instead of a fixed script. systemd orders the jobs of a transaction against those relations and starts everything whose prerequisites are already satisfied at once, so two units with no ordering relation between them come up in parallel rather than in sequence. Write a loop of After= lines and the journal prints 'Found ordering cycle' along with the job it deleted to break it - with no legal order available it drops an edge and carries on.

Workflow schedulersData engineering

An Apache Airflow DAG is a set of tasks with upstream dependencies, and by default the scheduler queues a task only after every upstream task has succeeded. That is the in-degree counter running over hours instead of microseconds: a finished task decrements its downstream counters and whatever reaches zero becomes runnable. Airflow rejects a cyclic definition when the file is parsed, for the same reason a spreadsheet does - a cycle has no run order at all.

Parallel buildsDeveloper tools

Ninja and make -j need more than a valid build order, they need to know what may run at the same time, and the ready set answers that directly. Every target with no unbuilt prerequisite is safe to start right now, so the size of the frontier is the parallelism available at that moment. A project whose dependencies form a long chain keeps that frontier one job wide, which is why throwing more cores at it changes almost nothing.

Why it works this way

Why in-degree counters instead of hunting for a vertex with no incoming edges

The literal reading of Kahn's algorithm is: scan the graph for a vertex nothing points at, remove it, scan again. That is correct and it costs V passes over the whole graph. The counter turns the scan into bookkeeping - one pass counts every incoming edge up front, and after that each edge is walked once more, when its source is placed, to decrement exactly one counter. A vertex joins the ready queue at the instant its last prerequisite is placed, so nothing is ever rescanned and the total work stays at V + E.

Why reverse postorder, and not the order DFS visits in

Visit order is wrong and a two-edge graph shows it. With a -> c and b -> c, a DFS that starts at a emits a then c, and only afterwards reaches b, so c lands before b even though the edge b -> c demands the opposite. The fix is to append a vertex on the way out rather than on the way in, because by then everything reachable from it is already in the list and it is guaranteed to sit after all of them. Reversing at the end turns that guarantee into the one a schedule needs.

A single visited flag reports cycles that are not there

The three states are not decoration. An edge into a finished vertex (state 2) is harmless - it was reached earlier down another branch and everything below it is already placed. Only an edge into a vertex still open on the current path (state 1) is a back edge, and only a back edge is a cycle. Collapse the two into one visited boolean and an ordinary diamond, a -> b, a -> c, b -> d, c -> d, gets rejected as cyclic the second time d is reached.

The order is not unique, and your container picks which one you get

Every vertex sitting in the ready set is a legal next choice, so most graphs have many valid orders and a test asserting one exact list is testing the deque, not the algorithm. Swap the ArrayDeque for a min-heap and you get the lexicographically smallest order, which is what a problem asks for when it wants one deterministic answer. A stack generally gives a different valid order again. Check a result by confirming it lists every vertex once and that every edge points forwards in it, never by comparing against a single expected list.

Read more

Next up

Binary Heap

Build a min heap

Next lesson: Binary Heap