A project scheduler models task dependencies as a directed graph: task A depends on B and C; B and C both depend on D; D has no dependencies. Which execution order is valid?
AA, B, C, D
BD, B, C, A
CB, A, D, C
DD, A, B, C
A valid topological order must place every dependency before the task that requires it. D must come first (no prerequisites), then B and C (both need D), then A (needs B and C). Options A and C put A or B before D, violating the dependency constraints. Option D places A before B and C, which also violates the constraints.
Question 2 Multiple Choice
You run Kahn's algorithm on a directed graph. After the algorithm terminates, several vertices were never added to the output sequence. What does this imply?
AThe graph has multiple valid topological orderings
BSome vertices have no outgoing edges
CThe graph contains a directed cycle
DThe graph is disconnected
In Kahn's algorithm, a vertex enters the queue only when its in-degree reaches 0 (all its prerequisites are satisfied). A vertex in a cycle can never reach in-degree 0, because other cycle members — which also never get processed — still point to it. If the algorithm exits with unprocessed vertices, those vertices are part of one or more cycles. This makes cycle detection a natural byproduct of topological sort: failure to produce a complete ordering proves a cycle exists.
Question 3 True / False
A directed graph that contains a cycle cannot have a valid topological ordering.
TTrue
FFalse
Answer: True
A topological ordering requires that for every edge u → v, u appears before v in the sequence. In a cycle A → B → C → A, A must come before B, B before C, and C before A — which means A must come before itself. No linear sequence can satisfy this. The existence of any cycle makes topological sorting impossible, which is why topological sort is defined only for DAGs (directed acyclic graphs).
Question 4 True / False
Most directed graph has at least one valid topological ordering.
TTrue
FFalse
Answer: False
Only directed acyclic graphs (DAGs) admit a topological ordering. Any graph with a directed cycle has no valid topological ordering, because a cycle creates a requirement that some vertex appear before itself in the sequence — an impossibility. The existence of a topological ordering is equivalent to the graph being a DAG.
Question 5 Short Answer
Why does Kahn's algorithm detect cycles as a side effect of performing topological sorting?
Think about your answer, then reveal below.
Model answer: Kahn's algorithm processes vertices greedily by in-degree: any vertex with in-degree 0 is ready to be placed next, and removing it decrements the in-degrees of its neighbors. Vertices in a cycle can never reach in-degree 0 because they always have an unprocessed predecessor inside the cycle pointing to them. If the algorithm finishes with vertices remaining (output count < total vertices), those leftover vertices must be part of cycles — their prerequisites were never satisfied because some prereq was also waiting for them.
This is the key insight linking topological sort to cycle detection: a successful topological sort and the absence of directed cycles are logically equivalent properties of a directed graph. Both Kahn's algorithm and the DFS-based approach exploit this equivalence, making them useful not just for ordering but for validating that a dependency graph is well-formed.