Topological Sort

What problem does this solve?

Some tasks can only be done after other tasks are finished. You cannot put on your shoes before your socks. You cannot compile a program before you compile the library it depends on. You cannot take a course before you take its prerequisite.

When you have a whole pile of such “X must come before Y” rules, you need a single order that respects all of them at once. That order is called a topological order, and computing it is called topological sort.

Before we go further, a few plain definitions:

• A graph is a set of nodes (things) connected by edges (links between things).
• A directed graph is one where each edge has a direction, drawn as an arrow. An edge from A to B means “A points to B”, which here we read as “A must come before B”.
• A cycle is a loop: you can follow arrows and return to where you started (A points to B, B points to C, C points back to A). If a loop exists, there is no valid order, because each node would have to come before itself.
• A DAG is a Directed Acyclic Graph: a directed graph with no cycles. “Acyclic” just means “no cycles”. Topological sort works only on a DAG.

Take this small DAG. Read every arrow as “must come before”, and notice the task is to line up all five nodes left to right so every arrow points forward.

graph LR
    A --> C
    B --> C
    C --> D
    C --> E
    D --> E

One valid topological order for this graph is A, B, C, D, E. Another is B, A, C, D, E. Both are correct, because in both of them every arrow points from an earlier node to a later node.

Where this shows up

• Build systems. To build a project, compile each file only after the files it depends on. The dependencies form a DAG; the build order is a topological sort.
• Task scheduling. A job pipeline where some jobs must finish before others start.
• Course prerequisites. You cannot enroll in a course until its prerequisites are done.
• Spreadsheet recalculation. A cell’s formula depends on other cells; recompute them in dependency order.

Key idea: in-degree

The in-degree of a node is the number of arrows pointing into it, meaning the number of things that must come before it. A node with in-degree 0 has no prerequisites, so it is safe to place first.

Once you place a node, you have “finished” it, so you can remove its outgoing arrows. That lowers the in-degree of the nodes it pointed to. Some of those may drop to 0, meaning they are now free to go next. Repeat until everything is placed. That is the whole algorithm.

Kahn’s algorithm

This is the in-degree approach, named after Arthur Kahn. It uses a queue: a line where you add items at the back and remove them from the front (first in, first out).

The steps:

1. Compute the in-degree of every node.
2. Put every node with in-degree 0 into the queue.
3. Repeat: take a node off the front of the queue, add it to the output, and for each node it points to, subtract 1 from that node’s in-degree. If any of those drops to 0, add it to the queue.
4. When the queue is empty, you are done.

Those four steps are really one loop with a queue-empty check as its exit; follow the “no” branch to see the dequeue-decrement-enqueue cycle repeat:

flowchart TD
    S[Compute all in-degrees] --> Q[Enqueue every node with in-degree 0]
    Q --> C{Queue empty?}
    C -- no --> P[Dequeue node n, append to output]
    P --> R[For each neighbor m: in-degree m minus 1]
    R --> Z{in-degree m is 0?}
    Z -- yes --> E[Enqueue m]
    Z -- no --> C
    E --> C
    C -- yes --> D[Done]

The code

We represent a graph as a dictionary: each key is a node, and its value is a list of the nodes it points to. (A dictionary is a lookup table of key-value pairs. A list is an ordered sequence of items.)

from collections import deque

def topological_sort(graph):
    # graph: dict where graph[node] is a list of nodes it points to.

    # Step 1: in-degree of every node, starting at 0.
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for neighbor in graph[node]:
            in_degree[neighbor] += 1

    # Step 2: queue holds every node with no remaining prerequisites.
    queue = deque(node for node in graph if in_degree[node] == 0)

    order = []
    while queue:
        node = queue.popleft()      # take from the front
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)  # now free to place

    # Step 3: if we placed every node, the order is valid.
    if len(order) == len(graph):
        return order
    return None   # a cycle exists, so no valid order

graph = {
    "A": ["C"],
    "B": ["C"],
    "C": ["D", "E"],
    "D": ["E"],
    "E": [],
}

print(topological_sort(graph))
# -> ['A', 'B', 'C', 'D', 'E']

deque (from Python’s standard collections module) is a double-ended queue. We use popleft() to remove from the front in constant time; a plain list would be slow at that.

Step-by-step trace of Kahn’s algorithm

Trace the code on the graph above. Starting in-degrees:

Both A and B start at in-degree 0, so both go into the queue. Now we watch the queue, the in-degree map, and the output change one step at a time.

Read step 1: we remove A, append it to the output, and lower C’s in-degree from 2 to 1. C is not 0 yet, so nothing new is enqueued. Step 2 removes B and lowers C from 1 to 0, so C enters the queue. And so on until the queue empties. Five nodes went in, five came out, so the order is valid.

Cycle detection for free

Kahn’s algorithm detects cycles with no extra work. In a cycle, every node in the loop has at least one prerequisite that is also in the loop, so its in-degree never reaches 0, so it is never enqueued. Those nodes never make it into the output.

That is why the final check is len(order) == len(graph). If the output is shorter than the graph, some nodes were stuck in a cycle and no valid order exists.

cyclic = {
    "X": ["Y"],
    "Y": ["Z"],
    "Z": ["X"],   # loops back to X
}

print(topological_sort(cyclic))
# -> None

The DFS approach (a second method)

There is another way to get a topological order using DFS (depth-first search: follow a path as deep as it goes before backing up). The idea: fully explore everything reachable after a node, then place that node. When a node’s descendants are all handled, add the node to a list. Reversing that list gives a topological order.

def topological_sort_dfs(graph):
    visited = set()        # nodes fully processed
    order = []             # filled back to front

    def visit(node):
        if node in visited:
            return
        visited.add(node)
        for neighbor in graph[node]:
            visit(neighbor)
        order.append(node)  # added after all descendants

    for node in graph:
        visit(node)

    order.reverse()
    return order

print(topological_sort_dfs(graph))
# -> ['B', 'A', 'C', 'D', 'E']

A node is added to order only after every node it points to has already been added. Since we then reverse, that node ends up before all of them, which is exactly what “must come before” requires. Note this returns a valid order that may differ from Kahn’s; both are correct.

This simple DFS version does not detect cycles. Catching a cycle needs a third state to mark nodes currently on the active path, so that returning to one signals a loop. Kahn’s algorithm handles cycles more directly, which is why it is the common first choice.

Complexity

Let V be the number of nodes (vertices) and E the number of edges.

• Time: O(V + E). Computing in-degrees looks at every edge once (E work) and every node once (V work). In the main loop, each node is enqueued and dequeued exactly once (V work), and each edge is examined exactly once when its source node is removed (E work). Add it up: a constant amount of work per node and per edge, so O(V + E).
• Space: O(V + E). The in-degree map holds one entry per node (V). The queue holds at most V nodes. The graph itself stores E edges. Together that is O(V + E).

This is optimal in the sense that you must at least read every node and every edge once to know the dependencies, and reading them is already O(V + E).

Common pitfalls

• The graph must be a DAG. If there is a cycle, no valid order exists. Always keep the final len(order) == len(graph) check; do not assume the input is acyclic.
• There is usually more than one valid order. When several nodes have in-degree 0 at the same time, any of them can go next. Kahn’s and the DFS method can return different but equally correct orders. Do not test for one exact list unless you fixed the tie-breaking rule (for example, always dequeue the alphabetically smallest node by using a sorted structure).
• Missing nodes in the dictionary. Every node that appears as a neighbor must also be a key in graph, even if its value is an empty list []. If a node like "E" is only ever a target and never a key, in_degree and the loops will miss it or raise an error.
• Using a list as a queue and calling pop(0). Removing from the front of a list is O(V) each time, making the whole algorithm O(V squared). Use collections.deque and popleft(), which is O(1).
• Recursion depth in the DFS version. A very long chain of nodes can exceed Python’s default recursion limit. Kahn’s algorithm uses a loop and has no such limit.

Practice

1. Modify Kahn’s algorithm so that when several nodes are free at once, it always picks the alphabetically smallest node next. (Hint: a sorted list or a heap can replace the plain queue.)
2. Given a list of course prerequisite pairs such as [("calc1", "calc2"), ("calc2", "calc3")], build the graph dictionary and return a valid order in which to take the courses, or report that the prerequisites contain a cycle.
3. Extend the algorithm to return not just one order but the length of the longest chain of dependencies (the minimum number of sequential steps if independent tasks could run in parallel).