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

This is a hands-on drill page for the parent topic. We will not re-derive the theory — instead we build a matrix of every situation a topological-sort problem can hand you, then solve one example per cell so you never meet a case you haven't already practised.

Before we start, one reminder of the two machines we will keep using (both from the parent note):

Recall The two engines in one breath

• DFS-topo: run Depth-First Search (DFS), append each vertex the moment it finishes (after its loop), then reverse the list.
• Kahn (BFS-topo): count each vertex's indegree (edges pointing in), start a queue with all indegree-0 vertices, emit one, decrement its neighbours, push any that hit 0.

---

The scenario matrix

Every topological-sort problem is really one of the cells below. We enumerate them first so the coverage is provable, not accidental.

Cell	Case class	What makes it special	Example
A	Single chain (linear graph)	Every vertex has exactly one predecessor → unique order	Ex 1
B	Multiple roots / branching	Several indegree-0 starts → many valid orders	Ex 2
C	Cycle present	No order exists — must be detected, not answered	Ex 3
D	Degenerate: no edges	All vertices are roots → any permutation works	Ex 4
E	Degenerate: single vertex / empty graph	Limiting smallest inputs	Ex 4
F	Disconnected components	Two independent DAGs interleave freely	Ex 5
G	Diamond (re-converging paths)	A vertex waits on two paths — indegree > 1	Ex 6
H	Real-world word problem	Translate English "before" into edges first	Ex 7
I	Exam twist: DFS vs Kahn give different valid answers	Both correct — prove it	Ex 8
J	Exam twist: self-loop $v\to v$	A one-vertex cycle — sneaky	Ex 9

Ten cells, nine examples (E folds into D's degenerate family). Let's go.

---

Example 1 — Cell A: the single chain (unique order)

Forecast: How many valid orders do you expect — one, or many? Guess before reading.

1. Compute indegrees. a:0, b:1, c:1, d:1. Why this step? Kahn always begins by asking "who has zero prerequisites?" Only a qualifies.
2. Emit a. Decrement b: b:0. Queue = [b]. Why this step? Removing a frees exactly one new vertex — a chain never offers a choice.
3. Emit b → c:0; emit c → d:0; emit d. Why this step? At every step the queue held exactly one element, so there was never a branch point.

Answer: a b c d — the only valid order.

Verify: Check each edge points forward in a b c d: a(pos 0)→b(1) ✅, b(1)→c(2) ✅, c(2)→d(3) ✅. Also #emitted = 4 = |V| ⇒ valid DAG. A chain of $n$ vertices always has exactly one order.

---

Example 2 — Cell B: multiple roots, many orders

Forecast: Two roots a and b feed into c. How many orderings survive?

1. Indegrees: a:0, b:0, c:2, d:1. Why this step? Both a and b are prerequisites of c, so c starts at indegree 2.
2. Start queue = [a, b] (order depends on how you enqueue). Why this step? Two indegree-0 vertices means the first decision is free — this is the source of multiple answers.
3. Pick a: c:2→1 (not 0 yet). Then pick b: c:1→0. Emit c → d:0. Emit d. Why this step? c waited for both parents — it could only leave after the second one.
4. Alternate branch: pick b first, then a → gives b a c d.

Answer: exactly two valid orders — a b c d and b a c d.

Verify: In a b c d: a→c (0<2) ✅, b→c (1<2) ✅, c→d (2<3) ✅. In b a c d: b→c (0<2) ✅, a→c (1<2) ✅, c→d ✅. Both have #emitted = 4. The order is not unique, exactly as the parent warned.

---

Example 3 — Cell C: a cycle (no order exists)

Forecast: Will the algorithm crash, loop forever, or stop cleanly with a signal?

1. Indegrees: a:1, b:1, c:1. Why this step? Every vertex has an incoming edge — look at the red loop in the figure. There is no indegree-0 vertex.
2. Build start queue: empty! Why this step? Kahn's engine needs a 0-indegree seed to begin; a cycle denies it one (parent note point 1).
3. The while loop never executes. order = [], so #emitted = 0. Why this step? An empty queue ends the loop immediately — this is the graceful stop, not a crash.
4. Apply the cycle test: #emitted (0) < |V| (3) ⇒ report CYCLE.

Answer: no topological order exists; Kahn detects it via #emitted < |V|.

Verify: #emitted = 0, |V| = 3, and 0 < 3 is True ⇒ cycle flagged correctly. See Cycle Detection in Directed Graphs. DFS would flag the same cycle by hitting a gray back edge on c→a.

---

Example 4 — Cells D & E: degenerate inputs (no edges, one vertex, empty)

Forecast: With zero constraints, how many orders exist for three isolated vertices?

1. Indegrees (D): x:0, y:0, z:0. Why this step? No edges means nobody points at anybody — every vertex is a root.
2. Queue holds all three; every pop is a free choice. Why this step? With no forward edges to respect, every permutation is valid — $3!=6$ orders.
3. Single vertex (E): indegree p:0, emit it → order p. #emitted = 1 = |V|. Why this step? The smallest non-empty case: one vertex, one trivial order.
4. Empty graph (E): |V| = 0, loop never runs, order = [], and #emitted (0) = |V| (0) ⇒ valid (a vacuous DAG). Why this step? Limiting case — the algorithm must not report a false cycle when there's simply nothing to sort.

Answer: (D) $6$ valid orders; (E) p is the unique order for one vertex, [] for the empty graph.

Verify: $3!=6$. Single-vertex: #emitted = 1 = |V| ⇒ valid, order length 1. Empty: 0 == 0 ⇒ valid, order length 0. No degenerate input trips a false cycle.

---

Example 5 — Cell F: disconnected components

Forecast: Two separate two-chains that ignore each other — how freely can they interleave?

1. Indegrees: a:0, b:1, c:0, d:1. Why this step? Two independent roots, a and c — the components never constrain each other.
2. Kahn queue starts [a, c]. Emit any root, its chain follows, but the other chain can be woven in anywhere as long as a<b and c<d. Why this step? The only rules are the two internal edges; everything else is free interleaving.
3. Count: choose which 2 of the 4 positions hold a,b (in that fixed order) → $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ interleavings. Why this step? This is the standard "merge two ordered sequences" count.

Answer: e.g. a c b d; there are 6 valid orders total.

Verify: $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$. Spot-check a c b d: a→b (0<2) ✅, c→d (1<3) ✅. A disconnected DAG is still a single DAG for Depth-First Search (DFS) — the outer loop just restarts on the next unvisited root.

---

Example 6 — Cell G: the diamond (re-converging paths)

Forecast: t is reachable two ways. Can t ever come out before both a and b?

1. Indegrees: s:0, a:1, b:1, t:2. Why this step? t has two incoming edges (a→t, b→t) — see the two coral arrows converging in the figure.
2. Kahn: emit s → a:0, b:0. Queue [a,b]. Emit a → t:2→1 (still blocked). Emit b → t:1→0. Emit t. Why this step? t waits until both paths deliver — this is what indegree-2 enforces.
3. DFS from s: dfs(s)→dfs(a)→dfs(t) finish t, finish a; back at s→dfs(b), t already done, finish b, finish s. Finished = [t,a,b,s]. Why this step? t finishes first (deepest), so it lands last after reversal — correct.
4. Reverse: s b a t.

Answer: Kahn → s a b t; DFS → s b a t. In both, t is last, s is first.

Verify: s a b t: s→a(0<1)✅ s→b(0<2)✅ a→t(1<3)✅ b→t(2<3)✅. s b a t: s→b(0<1)✅ s→a(0<2)✅ b→t(1<3)✅ a→t(2<3)✅. t never precedes a or b in any valid order — its indegree-2 forbids it.

---

Example 7 — Cell H: real-world word problem

Forecast: Translate first — how many tasks, and which are the free starting ones?

1. Turn "X before Y" into edges X→Y. Tasks: boil(B), teabag(T), pour(P), milk(M), drink(D). Edges: B→P, T→P, P→M, M→D. Why this step? "must be done before" is exactly a directed edge — this is the whole art of the Course Schedule Problem.
2. Indegrees: B:0, T:0, P:2, M:1, D:1. Why this step? P (pour) needs both B and T done — indegree 2, a diamond-like join.
3. Kahn: queue [B,T]. Emit B (P:1), emit T (P:0), emit P (M:0), emit M (D:0), emit D. Why this step? Each emission mirrors "this task's prerequisites are all done."

Answer: B T P M D (i.e. boil, teabag, pour, milk, drink). Also valid: T B P M D.

Verify: All 4 edges forward in B T P M D: B→P(0<2)✅ T→P(1<2)✅ P→M(2<3)✅ M→D(3<4)✅. #emitted = 5 = |V| ⇒ the recipe has no contradictory rule (no cycle).

---

Example 8 — Cell I: DFS and Kahn give different valid answers

Forecast: If two algorithms output different lists, can they both be right? Guess.

1. Kahn (parent note's walk-through): order = 4 5 0 2 3 1. Why this step? We always pulled an indegree-0 vertex; the tie between 4 and 5 was resolved by queue order.
2. DFS (start 5, then 4): finished = [0,1,3,2,5,4], reverse = 4 5 2 3 1 0. Why this step? DFS records on finish; the deepest-finishing vertices sink to the front after reversal.
3. These two lists differ (...0 2 3 1 vs ...2 3 1 0). Why this step? Wherever the graph offers a choice, the two engines may pick differently — neither is "the" answer.
4. Validity test: check every edge is forward in each list separately.

Answer: Kahn = 4 5 0 2 3 1, DFS = 4 5 2 3 1 0. Both valid.

Verify: For Kahn 4 5 0 2 3 1 positions {4:0,5:1,0:2,2:3,3:4,1:5}: 5→0(1<2)✅ 5→2(1<3)✅ 4→0(0<2)✅ 4→1(0<5)✅ 2→3(3<4)✅ 3→1(4<5)✅. For DFS 4 5 2 3 1 0 positions {4:0,5:1,2:2,3:3,1:4,0:5}: 5→0(1<5)✅ 5→2(1<2)✅ 4→0(0<5)✅ 4→1(0<4)✅ 2→3(2<3)✅ 3→1(3<4)✅. There is not one correct order.

---

Example 9 — Cell J: the self-loop twist

Forecast: b→b is a vertex pointing at itself. Does that count as a cycle?

1. Indegrees: a:0, b:2 (from a→b and b→b), c:1. Why this step? The self-loop contributes one incoming edge to b, so b starts at indegree 2.
2. Kahn: emit a → b:2→1. Queue now empty (b:1, c:1, neither is 0). Why this step? Removing a clears only one of b's two prerequisites; the self-edge can never be cleared, since b must be emitted to decrement it — but it can't be emitted while blocked.
3. #emitted = 1 < |V| = 3 ⇒ CYCLE. Why this step? A self-loop b→b says "b must come before b" — the tiniest impossible constraint.

Answer: no valid order — b→b is a length-1 cycle; Kahn stops with #emitted = 1 < 3.

Verify: #emitted = 1, |V| = 3, 1 < 3 is True ⇒ cycle reported. DFS catches it too: on visiting b (gray), the edge b→b points at a gray node = a back edge. See Directed Acyclic Graph (DAG) — a DAG forbids any cycle, self-loops included.

---

One-line recap of the matrix

Fill-in checks:

---

Connections

• Depth-First Search (DFS) — the engine behind the finish-order examples (1, 6, 8).
• Breadth-First Search (BFS) — the queue-driven engine in every Kahn walk-through here.
• Directed Acyclic Graph (DAG) — the precondition; Cells C and J are precisely non-DAGs.
• Cycle Detection in Directed Graphs — Examples 3 and 9 are cycle-detection in disguise.
• Course Schedule Problem — Example 7 is the tea-recipe version of it.