Noesis
3.5.7 · D5Graphs

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

1,678 words8 min read↑ Back to topic

Two words you must have locked in before starting:

  • indegree of a vertex = the number of edges pointing into it.
  • back edge = an edge that points to a vertex still open on the DFS recursion stack (marked GRAY) — the fingerprint of a cycle.

True or false — justify

Every line is a claim. Decide true/false, then give the reason (that is the whole point).

TF — "A topological order is unique for a given graph."
False. Whenever two vertices have no path between them (independent roots or branches), either can come first, so many valid orders exist. Uniqueness happens only when the DAG is a single chain .
TF — "Every directed graph has at least one topological order."
False. Only a DAG (Directed Acyclic Graph) does. A single cycle forces before and before — contradictory, so no ordering exists.
TF — "If a graph has no topological order, then it has a cycle."
True. The two are equivalent: an ordering exists iff the graph is acyclic, so the absence of any ordering is exactly a cycle.
TF — "Kahn's algorithm and DFS-based sort always output the same ordering."
False. They can produce different but equally valid orders. Kahn emits in arrival order (roots first as they hit indegree 0); DFS emits reverse finish order. Both respect every edge — that is all "correct" requires.
TF — "In a valid DAG, DFS never encounters a back edge."
True. A back edge means an edge into a still-open (GRAY) ancestor, which closes a cycle. A DAG has no cycles, so no back edge can occur.
TF — "An undirected graph can be topologically sorted."
False. Topological order is defined only for directed edges — "before/after" needs a direction. An undirected edge gives no ordering constraint at all.
TF — "A DAG always has exactly one vertex with indegree 0."
False. It has at least one, but can have many (e.g. 5→0, 4→1 has two roots, 4 and 5). "At least one" is what guarantees Kahn's can start; the count is not fixed.
TF — "Reversing all edges of a valid topological order gives another valid one."
True. If order makes every edge point forward, then reversing makes every edge point backward — which is a valid topological order of the graph with all edges reversed (the transpose). Same list, mirrored graph.
TF — "A self-loop still allows a topological order."
False. A self-loop is a length-1 cycle: must come before itself. So the graph is not a DAG and no order exists.

Spot the error

Each line describes a specific bug in the code or reasoning. Say what breaks and why.

"In DFS-topo I append each node the moment I enter it, then reverse."
Wrong. On entry the node's descendants aren't explored yet, so a descendant that must come later may land before it. Append on finish (after the neighbour loop), then reverse.
"In DFS-topo I append on finish but forget to reverse the list."
Wrong. The raw finish list has descendants first (they finish before ancestors), so edges point backward. Reversing flips finish-order into topo-order.
"In Kahn's I push a neighbour into the queue as soon as its indegree drops (becomes non-zero → something smaller)."
Wrong. Push a vertex only at the exact instant its indegree reaches 0 — that is the moment all its prerequisites are placed. Pushing earlier emits it before some prerequisite.
"My Kahn's loop finishes, order has fewer than nodes, so I just return it as the answer."
Wrong. Fewer than emitted means the leftovers all have indegree — a cycle. There is no valid order; you must report the cycle, not return a partial list.
"I detect cycles in DFS-topo by checking if a neighbour is already visited (BLACK)."
Wrong. A BLACK (fully finished) neighbour is fine — it's a normal forward/cross edge in a DAG. A cycle is signalled only by a GRAY neighbour (still on the stack = back edge).
"I run Kahn's but decrement indeg[v] before adding to the order."
Not wrong by itself, but be careful: you must decrement neighbours only after choosing to emit . The emit and the decrements happen together per popped node — order of those two operations for the same node doesn't change correctness, but never decrement for a node you haven't emitted.
"I compute indegrees once, then during Kahn's I recompute them from scratch each iteration."
Wrong (inefficient). Recomputing is per step, making the whole thing . Kahn's is precisely because you decrement in place as edges are removed.

Why questions

The reason is the answer — one sentence of "some node" is not enough.

Why does the node that finishes last in DFS belong at the front of the topological order?
Because a node finishes only after everything reachable from it finishes, so the last-finishing node has no unfinished successors — nothing must come before it, so it's a natural first (root).
Why does a DAG always contain at least one indegree-0 vertex?
If every vertex had an incoming edge, you could walk backward along incoming edges forever; with finitely many vertices you'd revisit one, forming a cycle — contradicting "acyclic."
Why does "emitted count " prove the graph is a DAG in Kahn's?
Every emit removes a vertex with all prerequisites cleared; if any cycle existed, its vertices could never reach indegree 0 (each waits on another in the loop), so they'd stay unemitted and the count would fall short.
Why do both algorithms run in and not ?
Each vertex is processed once and each edge is examined once (DFS traverses every edge; Kahn's decrements once per edge). Work is proportional to vertices plus edges, not vertices squared.
Why can't we just sort vertices by their indegree to get a topological order?
Indegree is a local count; it ignores which vertices point in. Two vertices with equal indegree can have an edge between them, and a low-indegree vertex may still depend on a high-indegree one — the ordering must follow edges, not counts.
Why does Kahn's use a queue (or stack) rather than needing the "smallest indegree" each step?
Any indegree-0 vertex is instantly safe to emit — there's no "best" one, so a plain FIFO/LIFO of the ready set suffices; we never search for a minimum.
Why is topological sort the natural setup for shortest paths in a DAG (see Shortest Path in DAG)?
Processing vertices in topo order guarantees that when you relax edges out of , all paths into are already finalized, so one linear pass gives correct distances.

Edge cases

Degenerate and boundary inputs — the reader must never be surprised by these.

A graph with vertices but zero edges — what is its topological order?
Any permutation of the vertices is valid, since there are no edge constraints at all. Kahn's starts with all vertices in the queue; DFS finishes them in any DFS order and reverses.
A single vertex, no edges — valid order?
Yes, the trivial order [v]. It's a DAG (vacuously acyclic), emitted count .
A disconnected DAG (two separate components) — does topo sort still work?
Yes. The vertices of different components have no edges between them, so they may interleave freely; both algorithms handle it — DFS loops over all start vertices, Kahn's queue holds roots from every component.
A DAG that is one long chain — how many valid orders?
Exactly one, 0,1,2,...,n. Every pair is edge-constrained, leaving no freedom — the only case where topological order is unique.
Graph with a self-loop plus other valid edges — what happens in Kahn's?
The self-loop adds 1 to 's own indegree, so never reaches 0 and is never emitted; the final count is , correctly reporting a cycle (via Cycle Detection in Directed Graphs).
Two vertices with edges both ways ( and ) — result?
A 2-cycle: neither ever reaches indegree 0 in Kahn's (each waits on the other), and DFS sees a back edge. No topological order exists.
A DAG where one vertex has indegree 0 and outdegree 0 (isolated-ish) — where does it land?
It's ready from the start (indegree 0) and constrains nothing (no out-edges), so it can appear anywhere in the order — Kahn's may emit it first, DFS may finish it whenever it's picked.

Connections

  • Depth-First Search (DFS) — the finish-time machinery every DFS-based trap here relies on.
  • Breadth-First Search (BFS) — Kahn's is BFS steered by indegree.
  • Directed Acyclic Graph (DAG) — the precondition every edge case probes.
  • Cycle Detection in Directed Graphs — both "stuck" edge cases reduce to this.
  • Course Schedule Problem — the "is this ordering possible?" application.
  • Shortest Path in DAG — why topo order matters downstream.
  • Strongly Connected Components — where finish-order reasoning reappears.