Topological Sort

A topological sort orders the vertices of a directed acyclic graph so every edge points forward, respecting all dependencies.

Ordering dependencies

A topological sort of a directed acyclic graph (DAG) is a linear ordering of its vertices such that for every directed edge from u to v, u appears before v. It answers questions of the form: in what order can I do these tasks so that every prerequisite comes before the task that needs it? A cycle makes such an order impossible.

Two ways to compute it

Kahn's algorithm repeatedly removes a vertex with no remaining incoming edges, appending it to the order and decrementing its successors' in-degrees. The DFS method runs a depth-first search and lists vertices in decreasing order of finish time. Both run in O(V + E) and both detect a cycle: Kahn's if vertices remain when no zero-in-degree vertex exists, DFS if it finds a back edge.

• Time: O(V + E)
• Requires a directed acyclic graph
• Kahn's algorithm: repeatedly remove zero-in-degree vertices
• DFS method: reverse of finish-time order

from collections import deque
def topo_sort(graph, indeg):
    q = deque([v for v in graph if indeg[v] == 0])
    order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order) == len(graph) else None  # None if cycle

Order is not unique

A DAG usually has many valid topological orders, since vertices with no dependency between them can appear in either relative position. Kahn's algorithm can produce a specific one, such as the lexicographically smallest, by using a priority queue instead of a plain queue to pick among the available zero-in-degree vertices.

Where it is used

Topological sort schedules build systems that compile files in dependency order, resolves package installation order, sequences course prerequisites, and orders spreadsheet cell recalculation. It is also the first step for computing shortest or longest paths in a DAG in linear time, since processing vertices in topological order lets each be relaxed exactly once with no priority queue needed.