Questions: Topological Sort

Question 1

You run a topological sort algorithm on a directed graph and observe that Kahn's algorithm terminates with only 4 of the 6 nodes placed in the output. What can you conclude?

• A. The graph has a valid topological ordering, but the algorithm made an error
• B. The graph contains a cycle involving the 2 nodes not in the output
• C. The graph is disconnected and the 2 missing nodes are in a separate component
• D. The algorithm needs to be restarted from a different source node

Answer: (B)

In Kahn's algorithm, nodes are placed in the output only when their in-degree drops to zero — meaning all their prerequisites have been processed. If the algorithm terminates early, it means the remaining nodes each have at least one unprocessed prerequisite, which can only happen if they form a cycle (each node waiting for another in the cycle). Kahn's algorithm is a cycle detector precisely because of this: if output size < total nodes, a cycle exists.

Question 2

For the dependency graph A → C, B → C, B → D, A → D, which of the following is a valid topological ordering?

• A. C, D, A, B
• B. A, C, B, D
• C. A, B, C, D
• D. B, D, A, C

Answer: (C)

A valid topological ordering requires every node to appear before all nodes it points to. A → C means A must precede C; B → C means B must precede C; A → D means A must precede D; B → D means B must precede D. Option C (A, B, C, D) works: A before C ✓, A before D ✓, B before C ✓, B before D ✓. Option A fails because C appears before A and B, which are its prerequisites. Note that option C is not the only valid ordering — B, A, C, D and B, A, D, C also work, illustrating that topological sort is not unique.

Question 3

A DAG with 5 nodes can have more than one valid topological ordering.

• T. True
• F. False

Answer: True

Topological sort is not unique unless the graph is a single chain (each node has exactly one prerequisite). Whenever two nodes have no dependency relationship between them, either can appear first in a valid ordering. The number of valid orderings can be exponentially large for sparse graphs. Both the DFS-based algorithm and Kahn's algorithm produce one valid ordering, but the choice depends on traversal order — different orderings of the input can yield different valid topological sorts.

Question 4

A graph with a directed cycle has multiple valid topological orderings, since you can start the cycle at different points.

• T. True
• F. False

Answer: False

A graph with any directed cycle has no valid topological ordering at all — not multiple orderings, zero orderings. A topological ordering requires every edge u → v to have u before v. In a cycle A → B → C → A, we need A before B, B before C, and C before A simultaneously — a contradiction. No linear ordering can satisfy all three constraints. Topological sort is defined only for DAGs (directed acyclic graphs).

Question 5

How does Kahn's algorithm naturally detect that a graph contains a cycle, without any explicit cycle-checking code?

Model answer: Kahn's algorithm only enqueues nodes when their in-degree reaches zero — meaning all their predecessors have been processed. In a cycle, every node in the cycle has at least one predecessor that is also in the cycle, so no node in the cycle ever reaches in-degree zero. The algorithm empties its queue while these nodes remain unprocessed. After the algorithm finishes, if the output contains fewer nodes than the graph, the missing nodes must be in a cycle.

This is one of Kahn's algorithm's most elegant properties: cycle detection emerges automatically from the queue logic, with no additional bookkeeping. In contrast, the DFS-based algorithm requires explicit tracking of nodes currently on the recursion stack (gray nodes) to detect back edges, which indicate cycles. For applications where cycle detection matters — build systems, package managers, dependency validators — Kahn's approach can be more straightforward to implement correctly.