Topological sort

Ordering things that depend on each other

Many tasks must happen in a certain order. You must study Data Structures before Algorithms. A build tool must compile code before it links and packages it. In a recipe for masala chai, you boil the water before adding the tea leaves, and add the leaves before straining. Each rule "u must come before v" is a directed edge u → v.

A topological order (or topological sort) is a list of all the vertices in which every edge points forward: for each edge u → v, u appears before v. There are often many valid orders. If the graph has a cycle, such as "A before B" and "B before A", no order can work.

A directed graph with no cycle is called a DAG (directed acyclic graph). Every DAG has at least one topological order, and a directed graph has a topological order only if it is a DAG.

Kahn's algorithm (BFS style)

The in-degree of a vertex is the number of edges coming into it: how many things must happen before it. A vertex with in-degree 0 has nothing blocking it, so it can go first.

1. Count the in-degree of every vertex.
2. Put every vertex with in-degree 0 into a queue.
3. Take a vertex u from the queue and append it to the order.
4. For every edge u → v, remove that edge by lowering the in-degree of v by 1. If it becomes 0, put v in the queue.
5. Repeat until the queue is empty. If the order has fewer than n vertices, the graph has a cycle.

from collections import deque

def kahn(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    queue = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == n else []

print(kahn(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))   # Output: [0, 1, 2, 3]
print(kahn(2, [(0, 1), (1, 0)]))                   # Output: []

Why does a cycle leave vertices behind? Every vertex on a cycle has an incoming edge from another vertex on the same cycle. None of them can be the first to reach in-degree 0, so none of them ever enters the queue.

The DFS method

Run the three-colour DFS from topic 3. When a vertex FINISHES (all the vertices after it are done), append it to a list. That list is the post-order. Reverse it and you have a topological order, because a vertex always finishes after everything it points to. Meeting a grey vertex means a cycle.

def topo_dfs(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    state = [0] * n          # 0 new, 1 on the path, 2 done
    post = []

    def dfs(u):
        state[u] = 1
        for v in adj[u]:
            if state[v] == 1:
                raise ValueError("cycle")
            if state[v] == 0:
                dfs(v)
        state[u] = 2
        post.append(u)

    for u in range(n):
        if state[u] == 0:
            dfs(u)
    return post[::-1]

print(topo_dfs(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))   # Output: [0, 2, 1, 3]

Deterministic orders and levels

When several vertices have in-degree 0 at the same time, Kahn's algorithm may take them in any order. If a problem asks for the lexicographically smallest order (the smallest number first whenever there is a choice), replace the queue with a min-heap from heapq (Module 8). The cost grows to O(V log V + E).

Another common question: if you can do any number of ready tasks at once, how many rounds do you need? Run Kahn's algorithm one layer at a time, like level-by-level BFS. The number of layers is the answer, for example the minimum number of semesters to finish a set of courses.

Common mistakes

• Reversing the edge direction. In the course-schedule problem, [a, b] usually means "to take a you must first take b", so the edge is b → a. Fix: write the arrow down before coding.
• Forgetting the cycle check. Fix: compare len(order) with n at the end.
• Starting only from vertex 0 instead of from every vertex with in-degree 0. Fix: fill the queue with all of them.
• In the DFS method, forgetting to reverse the post-order. Fix: return post[::-1].
• Expecting one fixed answer when many orders are valid. Fix: if tests need one answer, use the heap version or check validity instead.