Introduction

Topological sort is a standard way to order the nodes of a directed acyclic graph so that every prerequisite appears before the item that depends on it. It is useful for build systems, course prerequisites, task scheduling, and anywhere you need dependency-aware ordering.

What topological sort requires

Topological sorting only makes sense on a directed acyclic graph, often shortened to DAG. If the graph contains a cycle, no valid topological ordering exists because some nodes would depend on each other in a loop.

For example, these edges form a valid dependency graph:

• 'cook -> eat'
• 'shop -> cook'
• 'plan -> shop'

But if you add eat -> plan, the graph becomes cyclic and cannot be topologically sorted.

Kahn's algorithm in Python

One of the clearest implementations is Kahn's algorithm. It repeatedly removes nodes with indegree zero, appends them to the result, and decreases the indegree of their outgoing neighbors.

1from collections import deque
2
3
4def topological_sort(graph):
5    indegree = {node: 0 for node in graph}
6
7    for node in graph:
8        for neighbor in graph[node]:
9            indegree[neighbor] = indegree.get(neighbor, 0) + 1
10            if neighbor not in graph:
11                graph[neighbor] = []
12
13    queue = deque([node for node, deg in indegree.items() if deg == 0])
14    order = []
15
16    while queue:
17        node = queue.popleft()
18        order.append(node)
19
20        for neighbor in graph[node]:
21            indegree[neighbor] -= 1
22            if indegree[neighbor] == 0:
23                queue.append(neighbor)
24
25    if len(order) != len(indegree):
26        raise ValueError("graph contains a cycle")
27
28    return order
29
30
31graph = {
32    "plan": ["shop"],
33    "shop": ["cook"],
34    "cook": ["eat"],
35    "eat": [],
36}
37
38print(topological_sort(graph))

The result is one valid ordering, such as plan, shop, cook, eat.

How the algorithm works

The indegree of a node is the number of incoming edges. Any node with indegree zero has no remaining prerequisites, so it is safe to emit first.

Then:

1. remove that node from the queue
2. add it to the output order
3. subtract one from the indegree of each neighbor
4. enqueue any neighbor whose indegree becomes zero

If nodes remain at the end but none has indegree zero, the graph contains a cycle.

Complexity

With an adjacency list representation, Kahn's algorithm runs in linear time relative to the graph size:

• 'O(V + E) time'
• 'O(V) extra space for indegrees and the queue'

That makes it suitable for large sparse graphs commonly found in dependency systems.

Depth-first search alternative

Another common approach is depth-first search with temporary visitation marks to detect cycles. That method is also valid, but Kahn's algorithm is often easier to explain when you want an explicit dependency queue.

If your use case naturally thinks in terms of prerequisites becoming available, Kahn's algorithm tends to feel more intuitive.

Common Pitfalls

The biggest mistake is trying to topologically sort a graph that is not acyclic. If a cycle exists, there is no correct order, and the algorithm should report that instead of silently returning a partial result.

Another issue is forgetting to include nodes with no outgoing edges in the graph representation. A node that only appears as a neighbor still needs to exist in the indegree map.

It is also easy to mutate the original graph structure accidentally while computing indegrees. If that matters, work on a copy or keep the traversal state separate.

Finally, remember that topological order is not always unique. Multiple valid orders can exist for the same DAG.

Summary

• Topological sort orders nodes in a directed acyclic graph so prerequisites come first.
• Kahn's algorithm uses indegree counts and a queue of ready nodes.
• If the graph contains a cycle, topological sorting should fail.
• An adjacency list plus indegree map gives an efficient O(V + E) solution.
• Multiple valid topological orders may exist for the same graph.