Topological sort — DFS-based, Kahn's algorithm (BFS-based): Visual walkthrough

Step 1 — What is the picture we are ordering?

WHAT. A graph is dots joined by arrows. The dots are called vertices (things: tasks, courses, jobs). An arrow $u \to v$ is a directed edge and it means " $u$ must come before $v$ " — do $u$ first, then $v$ .

WHY arrows and not plain lines. A plain line says "these two are related." An arrow says "there is a direction — a before/after." Ordering is all about before/after, so we need arrows, not lines.

PICTURE. Below is the exact graph we will use for the whole page. Read each arrow out loud: "5 before 0", "5 before 2", "4 before 0", "4 before 1", "2 before 3", "3 before 1".

Figure — Topological sort — DFS-based, Kahn's algorithm (BFS-based)

Step 2 — Why a loop makes ordering impossible

WHAT. We check the one situation where no ordering can exist: a cycle — a chain of arrows that comes back to its own start, like $a \to b \to c \to a$ .

WHY we must check it first. An ordering promises "every arrow points forward." A cycle demands $a$ before $b$ , $b$ before $c$ , and $c$ before $a$ . Chain those and you get " $a$ before $a$ " — a thing before itself. Impossible. So a topological order exists if and only if the graph is a DAG (no cycles). This is our precondition; without it nothing below works. (See Cycle Detection in Directed Graphs.)

PICTURE. Left: our DAG, which can be laid flat left-to-right. Right: a 3-cycle — try to lay it flat and one arrow always bends backward (red).

Step 3 — The DFS idea: finish last ⇒ go first

WHAT. DFS (Depth-First Search, see Depth-First Search (DFS)) picks a vertex, dives down an arrow, dives again, and again — going as deep as possible before backing up. A vertex is finished the moment we back out of it, i.e. after everything reachable from it is done.

WHY this ordering trick works. If I finish a vertex only after all its descendants (everyone downstream of its arrows) finish, then the vertex that finishes last has nothing that must come after it — it belongs at the front. So: record finish order, then flip it.

PICTURE. Three colours track a vertex's life: white = untouched, teal (gray) = currently on the dive (in progress), plum (black) = finished. Watch a single dive from 5.

Step 4 — Watch the finish times build up

WHAT. We run the full DFS on our graph: start at 5, dive to 0 (dead end, finish 0), back up, dive 5→2→3→1 (finish 1, then finish 3, then finish 2), back to 5 (finish 5); then start 4, its arrows already lead to black nodes, so finish 4.

WHY we append on finish, never on entry. On entry to a vertex we have not yet seen its descendants — one of them might have to come later, and we'd wrongly place it earlier. On finish, every descendant is already recorded (earlier in the list), so flipping puts them all after. This is the single most common bug.

PICTURE. The finish clock ticks 1,2,3,4,5,6. Each vertex is stamped with the tick at which it turned black.

Finish list (in the order they turned black): $[0, 1, 3, 2, 5, 4]$ . Reverse it ⇒ $452310$ . That is a valid topological order.

Step 5 — The one dangerous case for DFS: the back edge

WHAT. While diving, suppose an arrow $u \to v$ hits a vertex $v$ that is currently gray (still on the stack, above us). That arrow is a back edge.

WHY it matters. $v$ being gray means there is already a path $v ⇝ u$ (that's how we got down to $u$ under $v$ ). Add the arrow $u \to v$ and you have closed a cycle. In that instant DFS knows the graph is not a DAG — no ordering exists. That is how DFS detects cycles for free.

PICTURE. The teal path is the current gray stack $v ⇝ u$ ; the red arrow $u \to v$ snaps it into a loop.

Step 6 — Kahn's idea: peel off what has no prerequisites

WHAT. Now the other algorithm. For each vertex count its indegree — how many arrows point into it. A vertex with indegree 0 has no unmet prerequisite → it is safe to place next.

WHY indegree 0 is the key. An arrow into $v$ is a "you still owe this prerequisite" token. Zero incoming tokens = nothing owed = ready to go. This is Breadth-First Search (BFS) but driven by these counters instead of raw distance.

PICTURE. Every vertex is labelled with its indegree. The two zeros (4 and 5) glow — they are our starting set.

Step 7 — Peel, decrement, repeat

WHAT. Put every indegree-0 vertex in a queue. Pop one, emit it, and for each of its out-arrows drop the target's indegree by 1; if a target hits 0, push it. Repeat until the queue empties.

WHY every emitted edge points forward. When we emit $u$ , all of $u$ 's prerequisites were already emitted (that is why $u$ reached indegree 0). The arrow $u \to v$ only now lowers $v$ 's counter, so $v$ can only be emitted after $u$ . Forward guaranteed.

PICTURE. Six snapshots: the counters drain, zeros appear, the emitted line grows left-to-right.

Step	Queue (indeg 0)	Pop → Emit	Decrements
1	[4, 5]	4	0→1, 1→1
2	[5]	5	0→0✅, 2→0✅
3	[0, 2]	0	—
4	[2]	2	3→0✅
5	[3]	3	1→0✅
6	[1]	1	—

Kahn order: 4 5 0 2 3 1. Different from DFS's 4 5 2 3 1 0 — both are valid (see Course Schedule Problem for where this matters).

Step 8 — Kahn's degenerate case: the stuck leftovers

WHAT. What if the queue empties but some vertices were never emitted?

WHY it happens. Those leftover vertices all still have indegree $\geq 1$ . Their remaining incoming arrows come from each other — a cycle that never lets anyone reach 0. So Kahn detects a cycle by counting: if fewer than $∣ V ∣$ vertices were emitted, a cycle exists.

PICTURE. Nodes 4 and 5 emit fine; the mutual pair $x ⇆ y$ keeps each other above 0 and stays stuck (red).

The one-picture summary

Both algorithms produce a line where every arrow points rightward. DFS gets there by finishing then flipping; Kahn gets there by peeling off zero-indegree nodes and counting to $∣ V ∣$ . Same DAG, two lenses, both $O (V + E)$ .

Recall Feynman retelling — say it to a 12-year-old

You have chores where some must come before others (read the book before writing the report). You want one long to-do line where you never do a chore before something it needs.

Way 1 (DFS): Pick any chore and dive into everything it leads to first. The moment a chore is totally done — all its follow-ons handled — drop it face-down in a "done" pile. When everything's piled, the pile is upside-down, so flip it over. That flipped pile is a perfect order.

Way 2 (Kahn): Give each chore a number = how many things must come before it. Any chore showing 0 is ready — do it, cross it off its followers' lists (their numbers drop by one). New zeros appear; keep going. If you finish and chores are still stuck above zero, they secretly depend on each other in a loop and can never be ordered.

The magic both share: a chore is only ever placed after everything it depends on. That is exactly "every arrow points forward."

Connections

Depth-First Search (DFS) — the crawl that produces finish times.
Breadth-First Search (BFS) — the queue engine behind Kahn's.
Directed Acyclic Graph (DAG) — the no-cycle precondition.
Cycle Detection in Directed Graphs — back edge (DFS) / short count (Kahn).
Course Schedule Problem — where multiple valid orders show up.
Shortest Path in DAG — relax edges in this order for linear-time shortest paths.
Strongly Connected Components — reuses DFS finish ordering (Kosaraju).