A study plan, a project build, package dependencies: some tasks must come after others. Such dependencies are a directed graph: an edge u -> v means "u before v". Topological sort lines the nodes up so that every edge points from left to right.

The dependency graph of seven courses and a valid order
The dependency graph of seven courses and a valid order

A DAG and the order condition

  • An order exists only in a directed acyclic graph (DAG).
  • For every edge u -> v, u comes before v.
  • The order is usually not unique: independent nodes may come in any sequence.
  • With a cycle there is no order: a -> b -> a demands "a before b and b before a".

Kahn's algorithm

The indegree is the number of edges entering a node. A node with indegree 0 depends on nothing, so we can start there.

python
deps = {
    "python": ["algorithms", "databases"],
    "math": ["algorithms", "statistics"],
    "algorithms": ["ml"],
    "databases": ["web"],
    "statistics": ["ml"],
    "ml": [],
    "web": [],
}

indegree = {node: 0 for node in deps}
for node in deps:
    for nxt in deps[node]:
        indegree[nxt] += 1
print(indegree)
print("sources:", [n for n in deps if indegree[n] == 0])
text
{'python': 0, 'math': 0, 'algorithms': 2, 'databases': 1, 'statistics': 1, 'ml': 2, 'web': 1}
sources: ['python', 'math']
  1. Enqueue all nodes with indegree 0.
  2. Take a node from the queue and append it to the result.
  3. Decrease each neighbour's indegree by 1 and enqueue those that reach 0.
  4. Repeat until the queue is empty.