Topological Sort

Topological Sort | Algoryva

First, the naive way

Try every ordering

The most direct approach: generate all orderings of the nodes and return the first in which every arrow points forward.

It is correct and fine for four nodes, but n nodes have n! orderings: 10 nodes means 3.6 million, 20 nodes means more than 10¹⁸. The search also never explains *why* a cycle makes it impossible.

python

from itertools import permutations

def first_valid_order(n, edges):
    for order in permutations(range(n)):
        pos = {v: i for i, v in enumerate(order)}
        if all(pos[a] < pos[b] for a, b in edges):
            return list(order)
    return []

print(first_valid_order(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))   # [0, 1, 2, 3]
print(first_valid_order(3, [(0, 1), (1, 2), (2, 0)]))   # []

Cost: O(n! × E): unusable beyond about 10 nodes.

Worked by hand

Kahn's algorithm traced by hand

Six tasks with arrows A→C, B→C, B→D, C→E, D→E, E→F. In-degrees: A 0, B 0, C 2, D 1, E 2, F 1.

take	arrows removed	in-degrees that reach 0	queue after
A	A→C: in(C) 2→1	none	B
B	B→C: in(C) 1→0 · B→D: in(D) 1→0	C, D	C, D
C	C→E: in(E) 2→1	none	D
D	D→E: in(E) 1→0	E	E
E	E→F: in(F) 1→0	F	F
F	none	none	empty

1
The order
A, B, C, D, E, F. Every arrow points forward. Taking B before A would also have been valid: orders are not unique.
2
The count check
All 6 nodes were taken, so there is no cycle. If fewer than 6 had been taken, the rest would depend on a cycle.

Implementation

Kahn's algorithm in code

The algorithm is BFS where “neighbour is ready” means “its in-degree has just reached zero”.

Plan in plain steps

pseudocode

compute in-degree of every node
queue = all nodes with in-degree 0
while queue is not empty:
    take u, append it to the order
    for each arrow u → v: in-degree of v decreases by 1; if it is now 0, add v to the queue
if the order contains every node: success, else: there is a cycle

python

from collections import deque

def topo_order(n, edges):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in edges:
        g[a].append(b)
        indeg[b] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []

print(topo_order(6, [(0, 2), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]))   # [0, 1, 2, 3, 4, 5]
print(topo_order(4, [(0, 1), (1, 2), (2, 3), (3, 1)]))   # []
print(topo_order(3, []))   # [0, 1, 2]

Reading the code

›indeg[b] += 1 counts incoming arrows while the graph is built; g[a].append(b) records the outgoing ones.
›Each node enters the queue once, exactly when its last prerequisite is taken, so the whole thing is O(V + E).
›return order if len(order) == n else [] is the cycle check: fewer nodes than expected means some were never free.
›With no edges at all every node is free at the start, so the order is simply 0, 1, 2: a topological order is not unique, and ours depends on queue order.

Implementation

The DFS way: reverse finishing order

DFS finishes a node only after everything it points to is finished. So if you list nodes in the order they finish and then reverse that list, every node appears before everything it points to. To catch cycles, track three states: new, on the current path, finished. Meeting a node that is *on the current path* means we found a cycle.

python

def topo_dfs(n, edges):
    g = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
    state = [0] * n          # 0 = new, 1 = on the current path, 2 = finished
    order = []
    ok = True

    def go(u):
        nonlocal ok
        state[u] = 1
        for v in g[u]:
            if state[v] == 1:
                ok = False
            elif state[v] == 0:
                go(v)
        state[u] = 2
        order.append(u)

    for s in range(n):
        if state[s] == 0:
            go(s)
    return order[::-1] if ok else []

def is_valid(order, edges):
    pos = {v: i for i, v in enumerate(order)}
    return len(order) > 0 and all(pos[a] < pos[b] for a, b in edges)

edges = [(0, 2), (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]
result = topo_dfs(6, edges)
print(result)   # [1, 3, 0, 2, 4, 5]
print(is_valid(result, edges))   # True
print(is_valid([0, 1, 2, 3, 4, 5], edges))   # True
print(topo_dfs(3, [(0, 1), (1, 2), (2, 0)]))   # []

Reading the code

›state[v] == 1 means v is an ancestor on the current recursion path: an arrow back to it closes a cycle.
›order.append(u) happens after the loop over successors: finishing order. The final order[::-1] reverses it.
›The result [1, 3, 0, 2, 4, 5] differs from Kahn's [0, 1, 2, 3, 4, 5] but is_valid confirms both respect every arrow. Any valid order is correct unless the problem asks for a specific one (for example the lexicographically smallest, which needs a heap instead of a queue in Kahn).
›As with every recursive DFS, very deep graphs may need an explicit stack in Python.

Worked problem

Can you finish all courses?

The problem

There are n courses numbered 0 to n − 1 and a list of pairs [course, need], meaning you must take need before course. Return True if all courses can be finished.

Build a directed graph with an arrow need → course and count each course's in-degree.
Run Kahn's algorithm and count how many courses were taken.
All can be finished exactly when every course was taken (no cycle).

python

from collections import deque

def can_finish(n, prerequisites):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for course, need in prerequisites:
        g[need].append(course)
        indeg[course] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    done = 0
    while q:
        u = q.popleft()
        done += 1
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return done == n

print(can_finish(2, [[1, 0]]))   # True
print(can_finish(2, [[1, 0], [0, 1]]))   # False
print(can_finish(4, [[1, 0], [2, 1], [3, 2]]))   # True

Takeaway. Course Schedule is topological sort with the answer being the *count check* alone. No order needs to be stored, just done == n. The second example is a two-course cycle: each waits for the other.

Worked problem

Minimum time with parallel courses

The problem

Courses 1 to n each take time[i - 1] months. A relation [a, b] means course a must finish before course b can start. You can take any number of courses at once if their prerequisites are done. Find the minimum total time.

A course can start only when *all* its prerequisites have finished, so its finish time is its own duration plus the latest finish among its prerequisites.
That is a longest-path computation on a DAG, done by processing courses in topological order.
Courses with no prerequisites finish at their own duration. When a course is taken from the queue, update each successor: finish[v] = max(finish[v], finish[u] + time[v]).
The answer is the largest finish time overall.

python

from collections import deque

def minimum_time(n, relations, time):
    g = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)
    for a, b in relations:
        g[a].append(b)
        indeg[b] += 1
    finish = [0] * (n + 1)
    q = deque()
    for i in range(1, n + 1):
        if indeg[i] == 0:
            finish[i] = time[i - 1]
            q.append(i)
    while q:
        u = q.popleft()
        for v in g[u]:
            finish[v] = max(finish[v], finish[u] + time[v - 1])
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return max(finish)

print(minimum_time(3, [[1, 3], [2, 3]], [3, 2, 5]))   # 8
print(minimum_time(5, [[1, 5], [2, 5], [3, 5], [3, 4], [4, 5]], [1, 2, 3, 4, 5]))   # 12

Takeaway. Topological order gives a safe processing order for dynamic programming on a DAG: every predecessor is finished before a node is handled. “Longest path” sounds hard in general graphs but is linear on a DAG.

Wrap-up

Remember this

A topological order puts every task after its prerequisites; it exists exactly when the dependency graph has no cycle.
Kahn's algorithm repeatedly takes nodes with in-degree 0 and removes their arrows; leftover nodes mean a cycle.
The DFS version lists nodes by finishing time and reverses; a node on the current path signals a cycle.
Both run in O(V + E), and valid orders are usually not unique.
Processing a DAG in topological order solves longest-path and earliest-finish problems in linear time.

Cheat sheet

Arrow: A → B means A before B; build g[A].append(B), indeg[B] += 1
Kahn: queue of in-degree 0; take u; decrement successors; enqueue new zeros
Cycle check: len(order) < n ⇒ cycle
DFS version: append u after its successors; reverse the list; 3 states for cycles
Cost: O(V + E)
DAG DP: process in topological order: finish[v] = max(finish[v], finish[u] + t[v])

Top traps to avoid

Reversing the arrow direction when building the graph.
Not checking whether all nodes were processed.
Forgetting to reverse the DFS finishing order.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.When does a valid topological order exist?
2.In the lesson's six-node example, what is the in-degree of C (arrows A→C and B→C)?
3.After Kahn's algorithm finishes, only 4 of 7 nodes are in the order. What does that mean?
4.What is the time complexity of Kahn's algorithm on V nodes and E arrows?
5.“Given prerequisites, output an order in which to take all courses, or report it is impossible” is:
6.In the DFS method, why do we need three states instead of just visited/not visited?
7.Kahn's algorithm on edges 1->2, 1->3, 2->4, 3->4, always taking the smallest ready node. What is the order?
8.Kahn's algorithm on the cycle 1->2, 2->1. Does it process all nodes? Print len(order) == n.
9.What must a topological order satisfy?
10.Running time of Kahn's algorithm on n nodes and m edges?
11.Two courses: course 1 needs course 0 first. The edge is 0 -> 1. What order does Kahn's algorithm produce?
12.Why does topological sort work only on directed acyclic graphs?
13.Edges 1->2, 1->3, 2->3. After removing node 1 and its outgoing edges, what is the in-degree of node 3?
14.In Kahn's algorithm, when does a node become ready to output?
15.DFS-based topological sort on 1->2 and 2->3: output the reverse of the finishing order. What is the result?

Topological Sort

After this lesson you will be able to

Builds on

Unlocks

Getting dressed

Dependencies as a directed graph

Try every ordering

Some node must always be free to go first

Kahn's algorithm

What a cycle does

Kahn's algorithm traced by hand

Kahn's algorithm in code

Reading the code

The DFS way: reverse finishing order

Reading the code

Costs

Edge cases

Mistakes to avoid

How to spot a topological-sort problem

Can you finish all courses?

Minimum time with parallel courses

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up2 problems

Core5 problems

Application3 problems

Challenge1 problem