Introduction

Sorting objects by their dependencies so that every object appears after the objects it depends on is called topological sorting. This is used in build systems (compile dependencies before dependents), package managers (install prerequisites first), task schedulers (run prerequisite tasks first), and spreadsheet formula evaluation. A valid topological order exists only when the dependency graph has no cycles.

Modeling Dependencies as a Graph

Represent each object as a node and each dependency as a directed edge from prerequisite to dependent.

1# Task B depends on A, Task C depends on A and B, Task D depends on C
2dependencies = {
3    "A": [],
4    "B": ["A"],
5    "C": ["A", "B"],
6    "D": ["C"],
7}

This means A must come before B, both A and B must come before C, and C must come before D. A valid order is [A, B, C, D].

Kahn's Algorithm (BFS)

Kahn's algorithm processes nodes with zero incoming edges first, then removes their outgoing edges. This naturally produces a topological order.

1from collections import deque, defaultdict
2
3def topological_sort_kahn(dependencies):
4    # Build adjacency list and in-degree count
5    graph = defaultdict(list)
6    in_degree = defaultdict(int)
7
8    for node in dependencies:
9        in_degree.setdefault(node, 0)
10        for dep in dependencies[node]:
11            graph[dep].append(node)
12            in_degree[node] += 1
13
14    # Start with nodes that have no dependencies
15    queue = deque(node for node in in_degree if in_degree[node] == 0)
16    result = []
17
18    while queue:
19        node = queue.popleft()
20        result.append(node)
21        for neighbor in graph[node]:
22            in_degree[neighbor] -= 1
23            if in_degree[neighbor] == 0:
24                queue.append(neighbor)
25
26    if len(result) != len(in_degree):
27        raise ValueError("Cycle detected — no valid ordering exists")
28
29    return result
30
31
32deps = {
33    "A": [],
34    "B": ["A"],
35    "C": ["A", "B"],
36    "D": ["C"],
37    "E": ["D", "B"],
38}
39print(topological_sort_kahn(deps))
40# ['A', 'B', 'C', 'D', 'E']

If the result contains fewer nodes than the input, a cycle exists and no valid topological order is possible.

DFS-Based Topological Sort

A depth-first search approach marks nodes as visited and appends them to the result in post-order (after all descendants are processed), then reverses the result.

1def topological_sort_dfs(dependencies):
2    visited = set()
3    in_progress = set()
4    result = []
5
6    def visit(node):
7        if node in in_progress:
8            raise ValueError(f"Cycle detected involving {node}")
9        if node in visited:
10            return
11        in_progress.add(node)
12        for dep in dependencies.get(node, []):
13            visit(dep)
14        in_progress.remove(node)
15        visited.add(node)
16        result.append(node)
17
18    for node in dependencies:
19        visit(node)
20
21    return result
22
23
24deps = {"A": [], "B": ["A"], "C": ["A", "B"], "D": ["C"]}
25print(topological_sort_dfs(deps))
26# ['A', 'B', 'C', 'D']

The in_progress set detects cycles by catching back-edges during traversal.

Comparison

Both algorithms have the same time complexity. Kahn's is often preferred when you want a deterministic order (use a priority queue instead of a deque). DFS is more natural when the graph is already represented with adjacency lists.

Using Python's graphlib (3.9+)

Python 3.9 added graphlib.TopologicalSorter to the standard library.

1from graphlib import TopologicalSorter
2
3deps = {"D": {"C"}, "C": {"A", "B"}, "B": {"A"}, "A": set()}
4sorter = TopologicalSorter(deps)
5print(list(sorter.static_order()))
6# ['A', 'B', 'C', 'D']

TopologicalSorter also supports incremental processing with prepare(), get_ready(), and done() for parallel task execution.

Real-World Applications

Build systems: Makefiles and CMake compute build order by topological sort of source file dependencies.

Package managers: pip, npm, and apt resolve install order by topological sort of package dependency trees.

Spreadsheet formulas: Cells that reference other cells must be evaluated after their dependencies. Circular references are detected as cycles.

Common Pitfalls

• Not detecting cycles — an infinite loop or incorrect results occur if the graph contains circular dependencies. Always check for cycles explicitly.
• Assuming a unique topological order — multiple valid orderings usually exist. If determinism matters, sort candidates at each step (alphabetically or by priority).
• Confusing dependency direction — "A depends on B" means B must come first, so the edge goes from B to A in the adjacency list.
• Forgetting isolated nodes — nodes with no dependencies and no dependents still need to appear in the output.
• Using recursion on very deep dependency chains — DFS can hit Python's recursion limit. Use sys.setrecursionlimit() or switch to iterative DFS for deep graphs.

Summary

• Topological sorting orders objects so that dependencies come before dependents.
• Kahn's algorithm (BFS) removes zero-in-degree nodes iteratively; DFS appends nodes in post-order.
• Both run in O(V + E) time and detect cycles.
• Python 3.9+ provides graphlib.TopologicalSorter in the standard library.
• Always validate that the graph is acyclic before assuming a valid order exists.