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.

Function Contract

topological_sort(graph) expects a directed adjacency list where every vertex appears as a key, including vertices with no outgoing edges.

It returns an ordering of vertices. If the returned list is shorter than the number of vertices, the graph has a directed cycle and no valid topological order exists.

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.

This version assumes every vertex appears as a key in graph, even if it has no outgoing edges. A vertex with no outgoing edges should map to an empty list.

Step-by-Step Idea

The indegree of a vertex is the number of incoming prerequisite edges. A vertex with indegree zero has no unmet prerequisites, so it can be placed next in the order.

After placing that vertex, the algorithm removes its outgoing edges by reducing the indegree of its neighbors. Any neighbor that reaches indegree zero becomes ready.

DFS Alternative

Topological sort can also be built from DFS postorder. A node is added after all nodes reachable from it have been processed. Reversing that postorder gives a topological order when no cycle exists.

The indegree method is often easier for beginners because the meaning of “ready” is explicit.

Complexity

With an adjacency list, topological sort is O(V + E). It stores the indegree table, queue, and output order, which together use O(V) extra space beyond the graph.

Cycle Check

If a cycle exists, no node in that cycle can become ready because each node waits for another node in the same cycle. That is why the output order is shorter than the number of vertices.

Failure Example

If A -> B, B -> C, and C -> A, every vertex waits for another vertex in the same cycle. No vertex in the cycle can honestly come first, so no topological order exists.

The short output from Kahn’s algorithm is not a partial success. It is evidence that the dependency graph contains 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.

Topological sort is for directed acyclic graphs. An undirected graph with ordinary two-way edges does not have the same prerequisite meaning.

When To Use It

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

Use it when the problem asks for an order that respects “must come before” relationships.

The Main Point

Topological sort orders directed dependencies. It exists only when the graph has no directed cycle.