Topological Sort

Topological sort orders vertices in a directed acyclic graph so that every prerequisite comes before the thing that depends on it.

It is used for dependency and scheduling problems.

Core Idea

If there is an edge from A to B meaning A must come before B, then A must appear earlier in the topological order.

Topological sort only works when the directed graph has no directed cycle. A cycle would mean some items depend on each other in a way that cannot be ordered.

Python Example

from collections import deque
 
def topological_sort(graph):
    indegree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            indegree[neighbor] += 1
 
    queue = deque([node for node in graph if indegree[node] == 0])
    order = []
 
    while queue:
        node = queue.popleft()
        order.append(node)
 
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
 
    return order

If the returned order is shorter than the number of vertices, the graph had a cycle.

Common Confusions

Topological sort is not numeric sorting. It sorts by dependency constraints.

There may be more than one valid topological order. If two items are independent, either can appear first.

When To Use It

Use topological sort for course prerequisites, build steps, task scheduling, dependency resolution, and dynamic programming on directed acyclic graphs.