Algorithm Guidecomplexity: O(V+E)

Topological Sort

Arranges the vertices of a directed acyclic graph (DAG) in a line so that every edge points only forward. Kahn's algorithm keeps nodes with indegree 0 in a queue and emits them in turn, forming the basis of task scheduling, dependency resolution, and build ordering.

01Topological Sort

Explore How It Works

Starting topological sort. Count each node's indegree, then enqueue A·B, which have indegree 0.

Pop A from the queue and append it to the order. Remove edge A→C, lowering C's indegree from 2 to 1.

Pop B and append it to the order. B→C drops C's indegree to 0, so enqueue C.

Pop C. C→D and C→E drop D's and E's indegree to 0, so both enter the queue.

Pop D. D→F lowers F's indegree from 2 to 1, but it isn't 0 yet, so don't enqueue it.

Pop E. E→F drops F's indegree to 0, so enqueue F last.

Pop F and append it to the order. The queue is empty, so every node is now listed in topological order.

Done · topological order A → B → C → D → E → F. A valid ordering where every edge points only forward.

Live Python

1from collections import deque

2def topo_sort(graph, indeg):

# indeg==0 → queue: A, B

3 q = deque(v for v in graph if indeg[v] == 0)

4 order = []

5 while q:

6 u = q.popleft()

7 order.append(u)

8 for v in graph[u]:

9 indeg[v] -= 1

10 if indeg[v] == 0:

11 q.append(v)

12 return order

1 / 8

02 Understand It Simply

For Everyone

🔑How It Works

Orders tasks with dependencies so that every prerequisite comes first. If the graph has a cycle, no such order exists.

💡In Plain Words

Lines up the vertices of a directed graph so that 'what must come first' comes first.

It pulls out nodes with indegree 0 one at a time.

📍Where It's Used

–Task scheduling
–build dependencies
–course prerequisites

03 Python Implementation

A clean, readable reference implementation of the core logic of Topological Sort.

core_implementation.py

from collections import deque

def topo_sort(graph, indeg):
    q = deque(v for v in graph if indeg[v] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order