Topological Sort

A topological sort takes a directed acyclic graph (a DAG) and arranges its vertices into a linear order such that for every directed edge u -> v, u comes before v in the ordering. It answers a very practical question: “given a bunch of tasks with dependencies, in what order can I actually do them?” Course prerequisites, build systems that must compile files in the right order, package manager installs, and spreadsheet formula recalculation all reduce to this same problem.

Overview: How Topological Sort Works

Picture getting dressed in the morning: you must put on socks before shoes, and a shirt before a jacket, but the order between “put on socks” and “put on shirt” doesn’t matter. A topological sort produces a valid sequence – not necessarily the only valid one – that respects every “before” constraint. This only makes sense on a directed acyclic graph: if the graph has a cycle (task A depends on B, B depends on C, and C depends on A), there is no valid order, because every candidate “first” task turns out to depend on something later in the list.

There are two classic ways to compute a topological order, and both run in linear time.

Kahn’s Algorithm (BFS, using in-degree)

Kahn’s algorithm repeatedly picks a vertex that has no remaining unprocessed prerequisites – an in-degree of zero, meaning no incoming edges left – outputs it, and then conceptually removes it from the graph by decrementing the in-degree of everything it points to. Removing a processed vertex can create new in-degree-zero vertices, which get queued up in turn. A vertex’s in-degree is simply the count of edges pointing into it: the number of prerequisites it still has left. A first-in-first-out queue (collections.deque) drives the process, which is why it behaves like a breadth-first search even though the underlying graph isn’t explored strictly level by level.

DFS-Based Topological Sort

The second approach runs a depth-first search from every unvisited vertex. Each vertex is appended to a result list only after all of its outgoing paths have been fully explored – this is a “postorder”: children finish before their parent. Because every dependency of a vertex is guaranteed to finish its DFS call before that vertex does, reversing the postorder list gives a valid topological order. This is elegant and often quick to write in an interview, but it hides a subtle trap covered in Common Mistakes below: a plain visited set is not enough to detect cycles safely.

Both algorithms only work correctly, and only terminate with a full ordering, when the graph has no cycles. A well-written topological sort should detect a cycle and report it rather than silently returning a partial or bogus order – that distinction matters a lot for correctness, and is covered in depth below.

Time and Space Complexity

Let V be the number of vertices and E the number of edges. Both algorithms visit every vertex exactly once and examine every edge exactly once, so both run in O(V + E) time. There isn’t a meaningful best/average/worst-case split here, because a correct topological sort always has to look at the entire graph once to guarantee the result respects every dependency, regardless of the input’s shape.

Approach	Time	Space	Why
Kahn’s algorithm (BFS)	O(V + E)	O(V + E)	O(V) to build the in-degree map and queue; O(E) to build the adjacency list and decrement an in-degree once per edge.
DFS-based	O(V + E)	O(V + E)	O(V) for the visited set, result list, and recursion stack (worst case a single chain of V nodes); O(E) to walk every edge once across all DFS calls.

The adjacency list itself costs O(V + E) space either way, which is the standard representation for topological sort since most real dependency graphs are sparse (a task rarely depends on more than a handful of others). An adjacency matrix would cost O(V^2) space and time just to scan for edges – wasteful unless the graph is dense or you specifically need O(1) “is there an edge from u to v” lookups.

Examples

Example 1: Kahn’s Algorithm on a Small DAG

This example encodes a tiny dependency graph as an adjacency list and runs Kahn’s algorithm to produce a valid order.

from collections import deque


def topological_sort_kahn(graph: dict[int, list[int]]) -> list[int]:
    in_degree: dict[int, int] = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    queue: deque[int] = deque(node for node in graph if in_degree[node] == 0)
    order: list[int] = []

    while queue:
        current = queue.popleft()
        order.append(current)
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(graph):
        raise ValueError("Graph has at least one cycle; no topological order exists.")

    return order


graph = {0: [1, 2], 1: [3], 2: [3], 3: [4], 4: []}
result = topological_sort_kahn(graph)
print("Topological order:", result)

Output:

Topological order: [0, 1, 2, 3, 4]

The graph encodes 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3, and 3 -> 4. Only vertex 0 starts with an in-degree of 0, so it’s the only entry in the initial queue. Processing 0 decrements the in-degree of 1 and 2 down to zero, so both join the queue. Processing 1 decrements 3’s in-degree from 2 to 1 (not zero yet, since 3 still has an incoming edge from 2). Processing 2 finally brings 3’s in-degree to 0, queuing it; processing 3 then queues 4. The result respects every edge in the graph.

Example 2: Ordering Course Prerequisites

A more realistic use case: given a list of courses and (before, after) prerequisite pairs, find a valid enrollment order.

from collections import deque


def find_course_order(courses: list[str], prerequisites: list[tuple[str, str]]) -> list[str]:
    graph: dict[str, list[str]] = {course: [] for course in courses}
    in_degree: dict[str, int] = {course: 0 for course in courses}

    for before, after in prerequisites:
        graph[before].append(after)
        in_degree[after] += 1

    queue: deque[str] = deque(course for course in courses if in_degree[course] == 0)
    order: list[str] = []

    while queue:
        current = queue.popleft()
        order.append(current)
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(courses):
        raise ValueError("Cannot complete all courses: a prerequisite cycle exists.")

    return order


courses = ["calculus1", "calculus2", "linear_algebra", "stats", "ml_intro"]
prerequisites = [
    ("calculus1", "calculus2"),
    ("calculus1", "linear_algebra"),
    ("linear_algebra", "ml_intro"),
    ("calculus2", "stats"),
    ("stats", "ml_intro"),
]

order = find_course_order(courses, prerequisites)
print("Valid course order:", " -> ".join(order))

Output:

Valid course order: calculus1 -> calculus2 -> linear_algebra -> stats -> ml_intro

Only calculus1 starts with zero prerequisites, so it’s processed first, unlocking calculus2 and linear_algebra. calculus2 unlocks stats. Note that ml_intro needs both linear_algebra and stats to finish first (its in-degree starts at 2), so it can’t be queued until stats is processed last among its prerequisites – which is exactly what the trace shows.

Example 3: The DFS-Based Approach

Running the DFS-based algorithm on the exact same graph from Example 1 produces a different, but equally valid, ordering – a good reminder that topological order is rarely unique.

def topological_sort_dfs(graph: dict[int, list[int]]) -> list[int]:
    visited: set[int] = set()
    order: list[int] = []

    def dfs(node: int) -> None:
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        order.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)

    order.reverse()
    return order


graph = {0: [1, 2], 1: [3], 2: [3], 3: [4], 4: []}
result = topological_sort_dfs(graph)
print("Topological order (DFS):", result)

Output:

Topological order (DFS): [0, 2, 1, 3, 4]

Starting at 0, the DFS dives into neighbor 1 first, which dives into 3, which dives into 4. Vertex 4 has no neighbors, so it’s appended to order first, then 3, then 1 (each after its own neighbors finish). Back at 0’s second neighbor, 2, its only neighbor (3) is already visited, so 2 is appended next, and finally 0 is appended once both its neighbors are done. That gives the postorder [4, 3, 1, 2, 0]; reversing it produces [0, 2, 1, 3, 4] – a different but still fully valid order compared to Example 1’s [0, 1, 2, 3, 4], since both respect every edge in the graph.

How It Works, Step by Step (Kahn’s Algorithm)

Here is the full state of the queue and in-degree map at every step while processing the graph from Example 1 (0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3, 3 -> 4). Initial in-degrees are {0: 0, 1: 1, 2: 1, 3: 2, 4: 1} and the queue starts as [0].

Step	Popped	Order so far	In-degree updates	Queue after
1	0	[0]	1: 1 -> 0 (queued), 2: 1 -> 0 (queued)	[1, 2]
2	1	[0, 1]	3: 2 -> 1 (not queued yet)	[2]
3	2	[0, 1, 2]	3: 1 -> 0 (queued)	[3]
4	3	[0, 1, 2, 3]	4: 1 -> 0 (queued)	[4]
5	4	[0, 1, 2, 3, 4]	none	[]

When the queue empties, order has 5 entries, matching the graph’s 5 vertices – confirming no cycle was hiding anywhere.

Common Mistakes

Mistake 1: Building the In-Degree Map from Only the Graph’s Keys

Every vertex needs an entry in the adjacency list, even ones with no outgoing edges (“sink” vertices). If a vertex only ever appears as someone else’s neighbor and was never added as a key, incrementing its in-degree raises a KeyError.

graph = {0: [1], 1: [2]}  # node 2 is never added as a key
in_degree = {node: 0 for node in graph}
for node in graph:
    for neighbor in graph[node]:
        in_degree[neighbor] += 1  # KeyError: 2 is not a key in in_degree
print(in_degree)

This fails because in_degree is built from graph‘s keys (0 and 1 only), but vertex 2 is referenced as a neighbor without ever being added as its own key. The fix is to make sure every vertex – including pure sinks – gets a key in the adjacency list up front.

graph = {0: [1], 1: [2], 2: []}
in_degree = {node: 0 for node in graph}
for node in graph:
    for neighbor in graph[node]:
        in_degree[neighbor] += 1
print(in_degree)

Now every neighbor referenced is guaranteed to already be a key, so this safely prints {0: 0, 1: 1, 2: 1}.

Mistake 2: A DFS “Visited” Set Alone Doesn’t Detect Cycles

This is the subtle one. It’s tempting to write the DFS-based sort with a single visited set and assume that’s enough – but a vertex marked “visited” the moment its DFS call begins looks identical to one that’s fully finished. That means a cyclic back-edge to an ancestor still on the call stack is silently treated as “already handled” instead of being flagged as a cycle.

def topological_sort_dfs_buggy(graph: dict[int, list[int]]) -> list[int]:
    visited: set[int] = set()
    order: list[int] = []

    def dfs(node: int) -> None:
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        order.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)

    order.reverse()
    return order  # BUG: never checks whether the graph actually has a cycle


graph_with_cycle = {0: [1], 1: [2], 2: [0]}  # 0 -> 1 -> 2 -> 0
print(topological_sort_dfs_buggy(graph_with_cycle))

Tracing this: dfs(0) marks 0 visited, calls dfs(1), which marks 1 visited and calls dfs(2), which marks 2 visited. Vertex 2’s only neighbor is 0 – but 0 is already in visited (it was marked at the very start), so the code treats that edge as harmless and just skips it. The function confidently prints [0, 1, 2], a plausible-looking order, even though the graph is actually cyclic (0 -> 1 -> 2 -> 0) and has no valid topological order. That’s a silently wrong result, not a crash – exactly the kind of bug that’s easy to miss.

The fix is to track two sets instead of one: visited (fully finished) and in_progress (currently on the call stack). Hitting a neighbor that’s in_progress means you’ve found a back-edge to an ancestor – a real cycle.

def topological_sort_dfs_safe(graph: dict[int, list[int]]) -> list[int]:
    visited: set[int] = set()
    in_progress: set[int] = set()
    order: list[int] = []

    def dfs(node: int) -> None:
        in_progress.add(node)
        for neighbor in graph[node]:
            if neighbor in in_progress:
                raise ValueError("Graph has a cycle; no topological order exists.")
            if neighbor not in visited:
                dfs(neighbor)
        in_progress.remove(node)
        visited.add(node)
        order.append(node)

    for node in graph:
        if node not in visited:
            dfs(node)

    order.reverse()
    return order


graph_with_cycle = {0: [1], 1: [2], 2: [0]}
try:
    print(topological_sort_dfs_safe(graph_with_cycle))
except ValueError as error:
    print(error)

Output:

Graph has a cycle; no topological order exists.

This time, when dfs(2) examines neighbor 0, 0 is still in_progress (its call hasn’t returned yet), so the function correctly raises instead of returning a bogus order.

Best Practices

• Always validate that the graph is actually a DAG before trusting the result: with Kahn’s algorithm, compare len(order) to the total vertex count; with DFS, track an explicit “on the current call stack” set rather than relying on a single visited set.
• Use an adjacency list (a dict of lists, or collections.defaultdict(list)) for the typical sparse dependency graph; reach for an adjacency matrix only when the graph is dense or you need O(1) edge-existence checks.
• Prefer Kahn’s algorithm when you want cycle detection as a natural side effect (no extra bookkeeping needed), or when you want to process vertices level by level (e.g., “which tasks can start right now?”).
• Prefer the DFS-based approach when you’re already traversing the graph for another reason, or when recursion reads more naturally for the problem – but remember Python’s recursion limit (around 1000) makes naive recursive DFS risky on very large or deeply chained graphs; rewrite it iteratively with an explicit stack for those cases.
• Never use a mutable default argument (like a list) to accumulate results across recursive calls – it’s created once and shared across every call, silently corrupting results. Pass the accumulator explicitly or close over a local variable, as the examples above do.
• Remember that more than one valid topological order usually exists. If a problem needs a specific one (like the lexicographically smallest), swap the plain queue for a heapq min-heap so ties are broken by picking the smallest available vertex first.
• Don’t confuse “topological order” with “sorted order” – the result only respects the dependency edges you gave it and says nothing about numeric or alphabetical ordering unless you specifically break ties that way.

Practice Exercises

1. Is it a DAG? Write a function is_dag(graph: dict[int, list[int]]) -> bool that returns True if a topological order exists and False otherwise, using Kahn’s algorithm. Hint: compare the length of the produced order to the number of vertices.
2. Course Schedule II. Given num_courses: int and a list of prerequisite pairs [a, b] meaning “course a requires course b to be completed first,” return one valid course order as a list, or an empty list if it’s impossible. This is a well-known interview question – try solving it with Kahn’s algorithm first, then again with DFS.
3. Build order with multiple valid answers. Given build targets ["app", "utils", "network", "core"] and dependency pairs [("core", "utils"), ("utils", "network"), ("network", "app")] (the first of each pair must build before the second), compute a valid build order. Then write a checker function that verifies a proposed order is valid by confirming every dependency pair appears in the right relative order, rather than comparing against one fixed expected list, since more than one order can be correct.

Summary

• Topological sort orders the vertices of a directed acyclic graph (DAG) so that every edge u -> v has u appearing before v.
• Kahn’s algorithm repeatedly removes vertices with in-degree zero using a queue (BFS-style); it detects cycles naturally when the output order ends up shorter than the vertex count.
• The DFS-based approach appends each vertex to the result in postorder, after all its descendants, then reverses the result; it needs an explicit “in-progress” set – not just “visited” – to detect cycles correctly.
• Both approaches run in O(V + E) time and O(V + E) space, since every vertex and every edge is examined exactly once.
• A graph with a cycle has no valid topological order – always check for this rather than trusting an algorithm to silently produce a correct-looking but wrong result.
• More than one valid topological order usually exists; only rely on one exact ordering in tests if the problem guarantees uniqueness, such as via a heap-based tie-break.