GeeksforGeeks Medium

Topological Sort (Kahn's BFS)

Order the vertices of a DAG so every edge points forward. Kahn's algorithm uses in-degrees.

graphtoposortbfsin-degree

02

Intuition

A vertex is ready to be output only when every prerequisite is already out — and 'no remaining prerequisites' is exactly in-degree == 0. Start with all such vertices, and each time you output one, remove its edges, which may free others. If the process stalls before covering every vertex, the leftovers form a cycle.

How to spot this pattern

Peel off vertices with no remaining prerequisites. In-degree zero means nothing blocks you; removing a vertex decrements its neighbours, which may free them in turn. The count check at the end doubles as cycle detection — a cycle can never reach in-degree zero, so the queue stalls early.

03

Approach

1

Count incoming edges

Scan every adjacency list once, incrementing indeg[v] for each edge u → v. Vertices with in-degree 0 depend on nothing and can go first.

2

Peel in waves

Queue all zero-degree vertices. Pop one, append it to the order, and decrement the in-degree of each target — any that hits 0 is newly unblocked and joins the queue.

3

Cycle detection for free

In a DAG every vertex eventually reaches in-degree 0. If the output is shorter than V, the remaining vertices each still wait on another — that is a cycle, so no ordering exists.

04

Solution & live demo

▶1from collections import deque
▶2 
▶3def topo_sort_kahn(n, adj):
▶4    indeg = [0] * n
▶5    for u in range(n):            # count incoming edges
▶6        for v in adj[u]:
▶7            indeg[v] += 1
▶8    q = deque(v for v in range(n) if indeg[v] == 0)
▶9    order = []
▶10    while q:
▶11        v = q.popleft()           # nothing blocks v
▶12        order.append(v)
▶13        for u in adj[v]:
▶14            indeg[u] -= 1
▶15            if indeg[u] == 0:
▶16                q.append(u)
▶17    if len(order) < n:            # stalled -> cycle
▶18        return []
▶19    return order

05

Common pitfalls

Not detecting the stall

✗ Wrong

return order

✓ Right

if len(order) < n:
    return []
return order

A cyclic graph produces a partial order and the algorithm terminates quietly. Comparing the output length against n is the whole cycle test — no separate DFS colouring needed.

Enqueuing on every decrement

✗ Wrong

indeg[u] -= 1
q.append(u)

✓ Right

indeg[u] -= 1
if indeg[u] == 0:
    q.append(u)

A vertex with three prerequisites would enter the queue three times and be emitted before its dependencies are satisfied. It becomes ready only on the transition to zero.

Counting outgoing edges as in-degree

✗ Wrong

for u in range(n):
    indeg[u] += len(adj[u])

✓ Right

for u in range(n):
    for v in adj[u]:
        indeg[v] += 1

In-degree counts edges arriving at a vertex. Counting the adjacency list's length measures out-degree, which inverts the dependency direction and yields a reversed or invalid order.

06

Edge cases

Graph has a cycle

Fewer than V vertices are output; return empty / report failure.

Multiple valid orders

Any is acceptable; queue order decides which one appears.

No edges at all

Every vertex starts at in-degree 0 — any permutation is valid.

07

Complexity

Time

O(V + E)

Space

O(V)

Each edge is decremented exactly once.