Kahn's Algorithm

AlgorithmintermediateTopological Sort

Repeatedly place a vertex with in-degree zero and lower the counts of everything it points to.

Decision · step 2 of 8Topological Sort: Kahn's algorithm

Place 0, position 1. Its edges to 1, 2 are satisfied, so their counts drop. 1, 2 reached 0 and are ready.

Open in the player →or start at step 2

What you will see

In-degree counters on vertices; zero-in-degree vertices enter a queue; removing one decrements its targets.

How topological sort works →

Cost

Best	`O(V + E)`
Average	`O(V + E)`
Worst	`O(V + E)`
Space	`O(V)`

How you work with it here

play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.

Screen readers: Vertices announce name, discovery numbers where relevant and component; each step announces the structural conclusion (bridge found, component closed).

Reduced motion: Component colouring and ordering changes crossfade in place.

Before this

Directed Acyclic Graph Breadth-First Search

DFS Topological Sort DAG Shortest Path

Leads to

Topics that need this one first.

DAG Shortest Path Topological Sort

Taught by the same lesson

Topological Sort covers these too, in the same run.

Directed Acyclic Graph DFS Topological Sort Topological Sort