DSA Tracker

Visualize

Topological Sort (BFS - Kahn's)

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 that 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 = 6, edges = [[5,0],[5,2],[4,0],[4,1],[2,3],[3,1]] (a->b means a comes before b) — return a topological ordering using BFS.

Problem:Topological Sort (BFS - Kahn's)Medium

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

step 1 / 16

A directed acyclic graph

6 vertices, 6 directed edges, and an arrow a to b means a must come before b in the answer. We are asked 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 16 steps
  1. 6 vertices, 6 directed edges, and an arrow a to b means a must come before b in the answer. We are asked 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 1, 3 has 1, 4 has 0, 5 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. Vertices 4 and 5 both sit at 0 — 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 every vertex freed by the same round lines up behind the ones already waiting.
  4. Pop 4 from the front and append it to the order — it is the 1st vertex out, and it is safe because its count is 0. Order so far: 4; 5 still wait in the queue.
  5. Now that 4 is out, each arrow leaving it is settled, so 0 drops to 1 and 1 drops to 1. Nothing hit 0 yet — 0 and 1 still have another arrow to clear, so they must keep waiting.
  6. Pop 5 from the front and append it to the order — it is the 2nd vertex out, and it is safe because its count is 0. Order so far: 4, 5; the queue is empty for now.
  7. Now that 5 is out, each arrow leaving it is settled, so 0 drops to 0 and 2 drops to 0. 0 and 2 hit 0 and join the back of the queue.
  8. Pop 0 from the front and append it to the order — it is the 3rd vertex out, and it is safe because its count is 0. Order so far: 4, 5, 0; 2 still wait in the queue.
  9. No arrow leaves 0, so no count changes and nothing new becomes ready.
  10. Pop 2 from the front and append it to the order — it is the 4th vertex out, and it is safe because its count is 0. Order so far: 4, 5, 0, 2; the queue is empty for now.
  11. Now that 2 is out, each arrow leaving it is settled, so 3 drops to 0. 3 hit 0 and joins the back of the queue.
  12. Pop 3 from the front and append it to the order — it is the 5th vertex out, and it is safe because its count is 0. Order so far: 4, 5, 0, 2, 3; the queue is empty for now.
  13. Now that 3 is out, each arrow leaving it is settled, so 1 drops to 0. 1 hit 0 and joins the back of the queue.
  14. Pop 1 from the front and append it to the order — it is the 6th vertex out, and it is safe because its count is 0. Order so far: 4, 5, 0, 2, 3, 1; the queue is empty for now.
  15. No arrow leaves 1, so no count changes and nothing new becomes ready.
  16. The queue drained after all 6 vertices, so the order is [4, 5, 0, 2, 3, 1]. Every arrow in the picture points from an earlier vertex to a later one — that is the definition of a topological order. Had the count come up short, the missing vertices would form a cycle.

Now solve it yourself

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

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