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

We reuse one running graph throughout so the figures stay familiar.

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

Level 1 — Recognition

Exercise 1.1

Which of these directed graphs can be topologically sorted?

(a) $a \to b, b \to c, c \to a$
(b) $a \to b, a \to c, b \to c$
(c) a single vertex $x$ with no edges.

Recall Solution 1.1

A topological order exists if and only if the graph is a DAG (no directed cycle).

(a) $a \to b \to c \to a$ is a cycle → no ordering. Following the arrows brings you back to $a$ , forcing $a$ before $a$ .
(b) No cycle. Valid order: $a, b, c$ . Yes.
(c) One vertex, no edges, trivially a DAG. Order is just $x$ . Yes.

Answer: (b) and (c).

Exercise 1.2

In Kahn's algorithm, which vertices of the running graph $G$ form the starting set (the initial queue)?

Recall Solution 1.2

The starting set is all vertices with indegree 0 — no arrows point into them, so they have no unmet prerequisites. Indegrees: $0 : 2, 1 : 2, 2 : 1, 3 : 1, 4 : 0, 5 : 0$ . Answer: ${4, 5}$ . (Look at the red vertices in the figure above — they have no incoming arrows.)

Level 2 — Application

Exercise 2.1

Run Kahn's algorithm on the running graph $G$ . When there is a tie (several indegree-0 vertices), always pop the smallest-numbered vertex. Give the full step table and the final order.

Recall Solution 2.1

We keep a queue of indegree-0 vertices. Pop the smallest, emit it, and decrement each neighbour's indegree; if a neighbour hits 0, push it.

Step	Queue (indeg 0)	Pop	Emit	Decrements	New zeros
1	[4, 5]	4	4	$0 \to 1$ , $1 \to 1$	—
2	[5]	5	5	$0 \to 0$ , $2 \to 0$	0, 2
3	[0, 2]	0	0	—	—
4	[2]	2	2	$3 \to 0$	3
5	[3]	3	3	$1 \to 0$	1
6	[1]	1	1	—	—

Order: $4, 5, 0, 2, 3, 1$ . Emitted count $= 6 = ∣ V ∣$ , so $G$ is a valid DAG.

Exercise 2.2

Run the DFS-based algorithm starting the outer loop at vertex $5$ , then $4$ (visit neighbours in increasing order). Record vertices on finish, then reverse.

Recall Solution 2.2

We append each vertex only after every vertex reachable from it has finished, then reverse.

dfs(5): go to $0$ → $0$ has no unvisited out-edges → finish 0. Back at $5$ , go to $2$ → $2 \to 3$ → $3 \to 1$ → finish 1, finish 3, finish 2, finish 5.
dfs(4): neighbours $0, 1$ already done → finish 4.
Finish list (in order of finishing): $[0, 1, 3, 2, 5, 4]$ .
Reverse $\Rightarrow 4, 5, 2, 3, 1, 0$ .

Note this differs from the Kahn order in 2.1 — both are valid, because the ordering is not unique.

Level 3 — Analysis

Exercise 3.1

For the running graph, how many distinct valid topological orders exist? Show the reasoning, not just a count.

Recall Solution 3.1

An order is valid iff it respects every "before" constraint. Constraints from the edges: $5 < 0, 5 < 2, 4 < 0, 4 < 1, 2 < 3, 3 < 1$ Think of building the sequence left-to-right by repeatedly choosing any current indegree-0 vertex (exactly Kahn's freedom). We count all such choice-trees.

Track available sets step by step:

Start: ${4, 5}$ available → 2 choices.

Rather than a messy tree, count by a cleaner argument. The "must-before" relations chain as $5 < 2 < 3 < 1$ and $4 < 1$ , plus $5 < 0$ and $4 < 0$ . Vertex $0$ only needs $4, 5$ done; vertex $1$ needs $3$ and $4$ done.

Enumerate by hand (systematic): the linear extensions are

$4, 5, 0, 2, 3, 1$ · $4, 5, 2, 0, 3, 1$ · $4, 5, 2, 3, 0, 1$ · $4, 5, 2, 3, 1, 0$ $5, 4, 0, 2, 3, 1$ · $5, 4, 2, 0, 3, 1$ · $5, 4, 2, 3, 0, 1$ · $5, 4, 2, 3, 1, 0$ $5, 2, 4, 0, 3, 1$ · $5, 2, 4, 3, 0, 1$ · $5, 2, 4, 3, 1, 0$ $5, 2, 3, 4, 0, 1$ · $5, 2, 3, 4, 1, 0$

Counting these gives 13 distinct valid orders.

Answer: 13. The point: multiplicity comes from independent roots ( $4$ and $5$ ) and from $0$ being free to slide anywhere after both $4, 5$ .

Exercise 3.2

In the running graph, at which exact moment during Kahn's run does vertex $0$ become available (indegree hits 0)? Explain why it can then be placed anywhere until it is popped.

Recall Solution 3.2

$0$ 's prerequisites are $4$ and $5$ (edges $4 \to 0$ , $5 \to 0$ ), so $indeg (0) = 2$ . It reaches 0 only after both $4$ and $5$ are emitted — that is step 2 in the table of 2.1. Once available, $0$ has no outgoing edges, so placing it does not create or block any new zero. Therefore it can be emitted at any later step without violating a constraint — this freedom is exactly why multiple valid orders exist.

Level 4 — Synthesis

Exercise 4.1 (Course Schedule)

You must take 4 courses. Prerequisites (edge $a \to b$ = " $a$ before $b$ "): $0 \to 1, 1 \to 2, 2 \to 3, 3 \to 1$ Can you finish all courses? If yes give an order; if no, explain. (This is the Course Schedule Problem pattern.)

Recall Solution 4.1

Follow the arrows: $1 \to 2 \to 3 \to 1$ is a directed cycle. Kahn confirms it: Indegrees: $0 : 0, 1 : 2, 2 : 1, 3 : 1$ . Start queue $= {0}$ .

Pop $0$ , emit $0$ , decrement $1$ ( $2 \to 1$ ). No new zero.
Queue empty. Emitted count $= 1 < 4 = ∣ V ∣$ . Fewer than $∣ V ∣$ emitted ⇒ a cycle remains among ${1, 2, 3}$ . Answer: No — the courses cannot all be finished; $1, 2, 3$ form a prerequisite loop.

Exercise 4.2 (Shortest Path in a DAG)

Using the running graph $G$ with every edge weight $= 1$ , compute the shortest distance from vertex $4$ to every reachable vertex by relaxing edges in the topological order $4, 5, 0, 2, 3, 1$ . (Background: Shortest Path in DAG.)

Recall Solution 4.2

Initialise $dist [4] = 0$ , all others $= \infty$ . Relaxing an edge $u \to v$ means: if $dist [u] + 1 < dist [v]$ , set $dist [v] = dist [u] + 1$ . Process vertices in topo order so every $u$ is finalised before its edges are used.

Process $4$ (dist 0): edges $4 \to 0$ , $4 \to 1$ → $dist [0] = 1$ , $dist [1] = 1$ .
Process $5$ (dist $\infty$ , unreachable from 4): skip its edges (relaxing from $\infty$ does nothing).
Process $0$ (dist 1): no out-edges.
Process $2$ (dist $\infty$ ): skip.
Process $3$ (dist $\infty$ ): skip.
Process $1$ (dist 1): no out-edges.

Distances from 4: $dist [0] = 1, dist [1] = 1$ ; vertices $2, 3, 5$ are unreachable ( $\infty$ ). Why topo order works: when we finalise $u$ , all paths into $u$ came from earlier (already-finalised) vertices, so $dist [u]$ is already correct.

Level 5 — Mastery

Exercise 5.1 (Prove the DFS property)

Prove: for a DAG, in a DFS every edge $u \to v$ satisfies $f (u) > f (v)$ , where $f (x)$ is the finish time. (This is the correctness core of Depth-First Search (DFS)-based topo sort.)

Recall Solution 5.1

Consider the moment DFS first discovers $u$ (colours it gray). Look at $v$ 's colour, three exhaustive cases:

$v$ white (undiscovered): DFS will recurse into $v$ from $u$ (directly or via other white descendants), so $v$ becomes a descendant of $u$ in the DFS tree. Descendants finish before their ancestor pops, hence $f (v) < f (u)$ . ✅
$v$ black (already finished): then $v$ finished before we even started $u$ , so $f (v) < f (u)$ . ✅
$v$ gray (on the stack): gray means there is an active path $v ⇝ u$ . Together with edge $u \to v$ this closes a directed cycle — impossible in a DAG. So this case never occurs.

In cases 1 and 2 (the only ones possible), $f (u) > f (v)$ . Therefore sorting vertices by decreasing finish time places $u$ before $v$ for every edge. $■$

Exercise 5.2 (Kahn always starts)

Prove: every non-empty DAG has at least one vertex with indegree 0, so Kahn's algorithm can always begin (and, by induction, always finishes).

Recall Solution 5.2

Suppose, for contradiction, every vertex has indegree $\geq 1$ . Pick any vertex $v_{0}$ ; it has an incoming edge from some $v_{1}$ . But $v_{1}$ also has indegree $\geq 1$ , so it has an incoming edge from $v_{2}$ , and so on: $\dots \to v_{2} \to v_{1} \to v_{0}$ . There are only $∣ V ∣$ vertices, so this backward walk must repeat a vertex within $∣ V ∣ + 1$ steps. A repeated vertex on a directed walk means a directed cycle — contradicting "DAG." Hence some vertex has indegree 0. ✅ Induction: emit it and delete its out-edges; the remaining graph is still a DAG (removing edges can't create a cycle), so it also has an indegree-0 vertex. Repeating empties the graph — Kahn terminates and emits exactly $∣ V ∣$ vertices. $■$

Exercise 5.3 (Reverse-graph trick)

Let $G^{R}$ be the running graph with every edge reversed. Claim: a valid topological order of $G^{R}$ is the reverse of a valid topological order of $G$ . Verify with the order $4, 5, 0, 2, 3, 1$ from Exercise 2.1.

Recall Solution 5.3

If $u \to v$ in $G$ , then $v \to u$ in $G^{R}$ ; and if $u$ before $v$ in a $G$ -order, then $u$ after $v$ in its reverse — exactly what $G^{R}$ demands. So reversing a valid $G$ -order gives a valid $G^{R}$ -order. Reverse of $4, 5, 0, 2, 3, 1$ is $1, 3, 2, 0, 5, 4$ . Check against $G^{R}$ edges ( $0 \to 5, 2 \to 5, 0 \to 4, 1 \to 4, 3 \to 2, 1 \to 3$ ): each edge points forward in $1, 3, 2, 0, 5, 4$ . For instance $1 \to 3$ : $1$ (pos 0) before $3$ (pos 1) ✅; $3 \to 2$ : pos 1 before pos 2 ✅; $0 \to 5$ : pos 3 before pos 4 ✅. All hold. Answer: $1, 3, 2, 0, 5, 4$ is a valid topo order of $G^{R}$ . This trick underlies Kosaraju's algorithm for Strongly Connected Components.

Active Recall

Recall Rapid self-test (cover the answers)

Kahn on running graph, smallest-first order? ::: $4, 5, 0, 2, 3, 1$
DFS-topo starting at 5 then 4, reversed order? ::: $4, 5, 2, 3, 1, 0$
How many valid topo orders does the running graph have? ::: 13
Course-schedule graph $0 \to 1 \to 2 \to 3 \to 1$ : finishable? ::: No — $1, 2, 3$ form a cycle.
DAG shortest path from 4, unit weights: dist to 0 and 1? ::: both 1 (2,3,5 unreachable)
Reverse of $4, 5, 0, 2, 3, 1$ as a $G^{R}$ order? ::: $1, 3, 2, 0, 5, 4$

Connections

Parent: Topological Sort — the algorithms these exercises drill.
Depth-First Search (DFS) — used in Exercises 2.2, 5.1.
Breadth-First Search (BFS) — Kahn's engine in Exercises 2.1, 3.2, 4.1.
Directed Acyclic Graph (DAG) — the existence precondition (Ex 1.1, 5.2).
Cycle Detection in Directed Graphs — Exercise 4.1's core.
Course Schedule Problem — Exercise 4.1.
Shortest Path in DAG — Exercise 4.2.
Strongly Connected Components — Exercise 5.3's reverse-graph trick.