Graph Algorithms

How Topological Sort Works

Topological sort arranges a directed acyclic graph so that every edge points forward. It is what a build system, a migration runner and a task scheduler are all computing.

A0 inB1 inC1 inD2 inE1 inF1 inG2 inH2 in
In the queue

Empty.

Order so far

Nothing yet.

  • Not reached
  • Waiting
  • Current
  • Finished
Speed

Step 1 of 21

Count the incoming edges of every node: A=0 B=1 C=1 D=2 E=1 F=1 G=2 H=2.

Counters

Placed
0/8
In the queue
0
Nodes
8
Edges
10

Settings

Graph

Topological sort

  1. 1count incoming edges per node
  2. 2queue = nodes with zero incoming
  3. 3while queue:
  4. 4 node = queue.shift()
  5. 5 output.push(node)
  6. 6 for each neighbour:
  7. 7 incoming[neighbour] -= 1
  8. 8 if incoming[neighbour] == 0:
  9. 9 queue.push(neighbour)

What each one answers

AlgorithmWhat it answersTimeNeeds
Breadth-firstFewest hops from the startO(V + E)A queue
Depth-firstReachability, one branch at a timeO(V + E)A stack
Cycle detectionDoes a cycle exist, and whereO(V + E)Node colours
Topological sortA valid order to do the work inO(V + E)No cycles
DijkstraCheapest path by edge weightO(E log V)Non-negative weights

V is the number of nodes and E the number of edges. Switch to the graph with a cycle and the topological sort gets stuck: once a cycle exists there is no valid order.

Complexity

BestAverageWorstExtra memory
O(V + E)O(V + E)O(V + E)O(V)

Only defined for acyclic graphs. Kahn's version detects a cycle for free: if fewer than V vertices come out, the rest are stuck in one.

How topological sort works

A topological order is a sequence of vertices where every edge points from earlier to later, so nothing appears before something it depends on. Kahn's algorithm produces one by repeatedly taking a vertex with no remaining incoming edges and removing it, which decrements its neighbours' counts and may expose new ready vertices. If the process stalls with vertices left over, those vertices form a cycle and no order exists.

  1. Count incoming edges for every vertex.
  2. Put every vertex with a count of zero into a queue — nothing has to happen before those.
  3. Take one out, append it to the order, and decrement the count of each of its neighbours.
  4. Any neighbour whose count reaches zero is now ready; add it to the queue.
  5. If the order ends up shorter than the vertex count, the remainder is a cycle.

Implementation

The same algorithm the visualiser is running, written to be read.

from collections import deque


def topological_sort(graph):
    incoming = {node: 0 for node in graph}
    for node in graph:
        for neighbour in graph[node]:
            incoming[neighbour] += 1

    # Everything that depends on nothing can go first.
    queue = deque(node for node, count in incoming.items() if count == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            incoming[neighbour] -= 1
            if incoming[neighbour] == 0:
                queue.append(neighbour)

    if len(order) != len(graph):
        raise ValueError("The graph has a cycle, so no topological order exists.")
    return order

When to use it

  • Use it to order builds, database migrations, module initialisation, and any task list with prerequisites.
  • Use it for course prerequisites, spreadsheet recalculation order, and resolving package dependency graphs.
  • Use it as a preprocessing step: shortest paths and longest paths on a DAG are linear-time once the vertices are in topological order.
  • Note that the order is usually not unique — several valid answers exist, and which one you get depends on the queue.

Check yourself

If the animation made sense, these should too.

How does Kahn's algorithm detect a cycle without a separate pass?

By counting what comes out. Every vertex with no remaining incoming edges is emitted, so if the order ends up shorter than the vertex count, the leftovers each still depend on something - and a set where everything depends on something else is a cycle.

Is a topological order unique?

Usually not. Any vertex with no unmet dependencies can go next, so a graph typically has many valid orders and which one you get depends on the queue. Code that relies on a particular order is relying on an implementation detail.

More graph algorithms