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.

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

python

▶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

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.

06

Complexity

Time

O(V + E)

Space

O(V)

Each edge is decremented exactly once.