Lesson 12 of 14

Ordering Dependencies with Topological Sort

Suppose an app must be tested before deployment, and built before testing. A topological sort places every prerequisite before the work that depends on it.

In build → test → deploy, arrows mean “must finish before.” This is different from sorting by number or name.

Find work that can start

A vertex’s indegree is the number of incoming edges. Zero indegree means no prerequisite remains.

1. Put all zero-indegree tasks in a queue.
2. Remove one and add it to the result.
3. Reduce the indegree of each task following it by one.
4. Enqueue tasks whose indegree has just become zero, and repeat.

This is Kahn’s algorithm.

from collections import deque

graph = {"build": ["test"], "test": ["deploy"],
         "deploy": []}
indegree = {node: 0 for node in graph}
for neighbors in graph.values():
    for node in neighbors:
        indegree[node] += 1

ready = deque(node for node in graph if indegree[node] == 0)
order = []
while ready:
    node = ready.popleft()
    order.append(node)
    for neighbor in graph[node]:
        indegree[neighbor] -= 1
        if indegree[neighbor] == 0:
            ready.append(neighbor)

if len(order) != len(graph):
    raise ValueError("Cycle detected")
print(order)

The output is ['build', 'test', 'deploy']. Every vertex appears as a dictionary key, including deploy, which has no outgoing edges.

Why cycles prevent an order

If A requires B to finish and B requires A to finish, neither can start. Topological sorting is possible for a directed acyclic graph (DAG). If the queue empties while vertices are missing from the result, a cycle exists.

Multiple zero-indegree tasks can give multiple valid orders. With adjacency lists, time is O(V+E). An order alone does not determine total completion time: task durations and rules for concurrent execution also matter.

Check your understanding

Cooking rice and preparing a side dish must both finish before eating. Is there only one valid order?