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
1/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

Scroll the table sideways for the rest of the columns.

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)

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

Python
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.
  • The order is usually not unique. Several valid answers exist, and which one you get depends on the queue.

More graph algorithms