DSA Tracker

Visualize

Topological Sort (Kahn's Algorithm)

Kahn's algorithm: output vertices as their incoming edges clear

time O(V + E)space O(V + E)

A topological order lists the vertices so every arrow points forward. Kahn's idea: a vertex with no incoming arrows can safely go first, and once it is out, the arrows leaving it no longer matter — so the vertices it pointed at may become safe too. Keep one number per vertex, its remaining incoming count, and a queue of vertices whose count has hit 0. Popping from the front and pushing newly freed vertices at the back is what makes it breadth-first. The picture draws one directed arrow per edge and shows the remaining count as a badge.

Details

Animated on: numVertices = 4, edges = [[3,0],[3,1],[2,1],[1,0]] (a->b means a comes before b) — return a topological ordering using Kahn's BFS algorithm.

Problem:Topological Sort (Kahn's Algorithm)Medium

Kahn's algorithm: output vertices as their incoming edges clear

step 1 / 11

A directed acyclic graph

4 vertices, 4 directed edges, and an arrow a to b means a must come before b. The task asks for an ORDER, so the plan is to output vertices one at a time and only ever output a vertex once everything pointing at it is already out.

Pseudocode
1FUNCTION topoSort(n, edges):
2  FOR v FROM 0 TO n - 1
3    indeg[v] <- 0
4  FOR EACH (a, b) IN edges
5    APPEND b TO next[a]
6    indeg[b] <- indeg[b] + 1
7  queue <- EVERY v WHERE indeg[v] = 0
8  order <- EMPTY LIST
9  WHILE queue NOT EMPTY
10    v <- REMOVE FIRST FROM queue
11    APPEND v TO order
12    FOR EACH w IN next[v]
13      indeg[w] <- indeg[w] - 1
14      IF indeg[w] = 0
15        APPEND w TO queue
16  RETURN order

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. 4 vertices, 4 directed edges, and an arrow a to b means a must come before b. The task asks for an ORDER, so the plan is to output vertices one at a time and only ever output a vertex once everything pointing at it is already out.
  2. Count the arrows pointing INTO each vertex: 0 has 2, 1 has 2, 2 has 0, 3 has 0. A vertex is safe to output exactly when that count is 0, so this one number per vertex is the whole state the algorithm needs.
  3. 2 and 3 sit at 0 already — nothing points at them, so they can go first. Seed the queue with them in index order; the queue is what makes this breadth-first, since vertices freed by the same round line up behind the ones already waiting.
  4. Pop 2 from the front and append it to the order — it is the 1st vertex out, safe because its count is 0. Order so far: 2; 3 still waits in the queue.
  5. Now that 2 is out, each arrow leaving it is settled: 1 drops to 1. Nothing hit 0 yet, so nothing new joins the queue.
  6. Pop 3 from the front and append it to the order — it is the 2nd vertex out, safe because its count is 0. Order so far: 2, 3; the queue is empty for now.
  7. Now that 3 is out, each arrow leaving it is settled: 0 drops to 1, 1 drops to 0. 1 hit 0 and joins the back of the queue.
  8. Pop 1 from the front and append it to the order — it is the 3rd vertex out, safe because its count is 0. Order so far: 2, 3, 1; the queue is empty for now.
  9. Now that 1 is out, each arrow leaving it is settled: 0 drops to 0. 0 hit 0 and joins the back of the queue.
  10. Pop 0 from the front and append it to the order — it is the 4th vertex out, safe because its count is 0. Order so far: 2, 3, 1, 0; the queue is empty for now.
  11. No arrow leaves 0, so no count changes and nothing new becomes ready.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Topological Sort (Kahn's Algorithm) in the editorAll Graph problemsBack to roadmap