Topological Sort

In Turkish: Topolojik Sıralama
Pronunciation: top-uh-LOJ-ih-kul sort

Updated September 30, 20263 min read

In short

Topological sort is an algorithm that orders the nodes of a directed acyclic graph so that for every edge from A to B, A comes before B in the resulting list.

What is a topological sort?

A topological sort takes a directed graph, where each edge points from one node to another, and lists all of its nodes in an order that respects every edge: if there is an edge from A to B, A appears before B. When edges mean must happen before, as with tasks and their prerequisites, the result is a valid order in which to do everything. A graph can have many valid topological orders, and it has at least one only if it is a directed acyclic graph (DAG), meaning it contains no cycles.

There are two standard algorithms, and both run in O(V + E) time, where V is the number of vertices and E the number of edges. Kahn's algorithm counts each node's incoming edges, starts with a queue of nodes that have none, and repeatedly removes a node from the queue, appends it to the output, and lowers its neighbors' counts, queueing any that drop to zero. The depth-first search approach adds each node to a list only after all of its descendants are finished, then reverses that list. If Kahn's algorithm stops before outputting every node, or DFS finds an edge back to a node still in progress, the graph has a cycle and no valid order exists.

Getting dressed is the classic example: socks must come before shoes and a shirt before a jacket, but you are free to put on your socks or your shirt first. Build tools use topological sorting to compile modules after the modules they import, package managers to install dependencies before the packages that need them, spreadsheets to recalculate cells after the cells they reference, and CI/CD pipelines and workflow schedulers to run jobs in dependency order. Course planners use it too, ordering classes so that prerequisites always come first.

Despite the name, topological sort is not a sorting algorithm in the usual sense: it doesn't compare values, and many valid answers can exist for the same graph. It is also different from a plain DFS or BFS traversal, which visits nodes in an order set by the starting point rather than by dependencies. And it only works on DAGs: circular dependencies, such as two packages that each require the other, make a topological order impossible, which is why tools report them as errors.

Key takeaways

A topological sort orders a directed graph's nodes so that every edge points forward in the list.
It exists only for directed acyclic graphs (DAGs).
Kahn's algorithm and the DFS-based method both run in O(V + E) time.
A graph often has many valid topological orders.
Build systems, package managers, and task schedulers use it to order work by dependencies.

Example

Kahn's algorithm in Pythonpython

from collections import Counter, deque

def topo_sort(graph):  # graph maps each task to the tasks that must wait for it
    indegree = Counter(a for targets in graph.values() for a in targets)
    queue, order = deque(n for n in graph if indegree[n] == 0), []
    while queue:
        node = queue.popleft()  # a task with no unfinished prerequisites
        order.append(node)
        for after in graph[node]:
            indegree[after] -= 1
            if indegree[after] == 0:
                queue.append(after)
    return order if len(order) == len(graph) else None  # None: there is a cycle

print(topo_sort({"shirt": ["jacket"], "socks": ["shoes"], "jacket": [], "shoes": []}))  # ['shirt', 'socks', 'jacket', 'shoes']

Readers ask

What is a topological sort used for?

It orders tasks that depend on each other, so each task comes after everything it needs. Build systems, package managers, spreadsheet recalculation, CI/CD pipelines, and database migration tools all rely on it.

Can a graph with a cycle be topologically sorted?

No. In a cycle, each node would have to come both before and after the others, which is impossible. Topological sort algorithms detect this case, which is how tools find circular dependencies.

Is a topological order unique?

Usually not. Any order that keeps every edge pointing forward is valid, so a graph with independent tasks has many valid orders; the order is unique only when a single path runs through every node.