Lesson

Topological Sort

The intuition: what comes first

You're getting dressed in the morning. Socks go on before shoes, a T-shirt before a jacket. But socks and the T-shirt can go on in either order. To keep it straight, you do this: pick any item you can already put on, because everything it needs is already on you. Put it on, and maybe some new items have "unlocked".

That's topological sorting: arranging tasks in an order where each one comes after everything it depends on.

Dependencies as a graph

Each task is a vertex. If A must be done before B, draw a directed edge A → B.

Let's take an example — building a project's modules:

Module	Number	Depends on
utils	0	—
db	1	utils
auth	2	utils
api	3	db, auth
app	4	api

Edges: 0→1, 0→2, 1→3, 2→3, 3→4.

One valid order is utils, db, auth, api, app. The order utils, auth, db, api, app is also valid. The answer is often not unique, and that's fine in an interview.

A cycle = impossible. If A waits for B and B waits for A, neither can go first. A topological order exists only for a graph without cycles (a DAG). That makes the same sort a cycle detector too.

Kahn's algorithm: in-degrees and a queue

A vertex's in-degree (indegree) is how many arrows point into it, i.e. how many unfinished dependencies it has. A vertex with indegree = 0 is ready to run right now.

The algorithm:

Compute indegree for every vertex.
Put every vertex with indegree = 0 into a queue.
While the queue isn't empty:
- take out a vertex v and append it to the answer;
- for each neighbor u (edge v → u), decrease indegree[u] by 1, since one dependency is done;
- if indegree[u] became 0, put u in the queue.
If the answer has fewer than n vertices, the graph has a cycle.

Let's run it on our example

Starting in-degrees. Only utils is free:

indegree: utils=0, db=1, auth=1, api=2, app=1

utils→null

the queue at the start

Take out utils. Its neighbors db and auth each lose a dependency, and both drop to 0:

after utils: db and auth are free

db→auth→null

queue: db, auth

Take out db, and api drops to 1. Not yet. Take out auth, and api drops to 0:

after db and auth: api is ready

Then api frees up app. The result:

utils→db→auth→api→app→null

topological order — all 5 vertices, no cycle

Code template

Vertices are numbered 0..n-1, and edges are given as [from, to] pairs. The function returns the order, or an empty list if there's a cycle.

from collections import deque

def topo_sort(n, edges):
    graph = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in edges:          # a must come before b
        graph[a].append(b)
        indeg[b] += 1
    q = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while q:
        v = q.popleft()
        order.append(v)
        for u in graph[v]:
            indeg[u] -= 1       # one dependency is done
            if indeg[u] == 0:
                q.append(u)
    return order if len(order) == n else []  # otherwise a cycle

Complexity

Time: O(V + E). Every vertex enters the queue once, and every edge is looked at once.
Memory: O(V + E) for the adjacency list, the in-degree array and the queue.

Where it shows up

Building modules and packages: in what order to compile (make, Gradle, npm/pip resolvers).
Course schedules: "to take course B, first complete A". Can you finish every course, and in what order?
The order of evaluating spreadsheet cells, database migrations, task pipelines (CI, Airflow).

The signal to use it: the problem mentions "depends on", "first / then", "prerequisite", "order".

How it sounds in an interview

"I'll build a directed graph: an edge from A to B if A has to be done first. I compute in-degrees and run Kahn's algorithm: put the vertices with no dependencies into a queue, take them out one by one, and decrease their neighbors' in-degrees. If I haven't processed every vertex at the end, there's a cycle and no answer. Time and memory are O(V + E)."

Common mistakes

Edge direction flipped. "B depends on A" is A → B, and it's B's indegree that goes up. Flip it and you get the order backwards.
Forgetting the cycle check. Vertices in a cycle never reach the queue, and the answer silently comes out shorter. Always compare len(order) with n.
Not every vertex counted. An isolated vertex with no edges must also end up in the answer. Fill the starting queue by iterating over all of 0..n-1, not just the vertices that appear in edges.
shift() in JS or slicing in a loop on large inputs. Use a head pointer.

Remember one sentence: "take whatever is already free, and free up the next ones". You can rebuild all of Kahn's algorithm from it in a minute.