Micro-questions over the topological sort module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. The idea

1. What is a topological order?

Answer

A linear list where every prerequisite node comes before every node that depends on it — equivalently, an arrangement in which every edge points forwards.

2. Give the getting-dressed illustration.

Answer

Underwear → Pants → Shoes, and Socks → Shoes. You cannot put shoes on before socks and pants, nor pants before underwear.

3. Give two valid orderings for that graph.

Answer

[Underwear, Socks, Pants, Shoes] and [Socks, Underwear, Pants, Shoes].

4. What does that show?

Answer

A graph can have multiple valid topological orderings. Where the constraints do not order two tasks, either may come first.

5. Name four production applications.

Answer

Build systems (Make, Bazel, Webpack), package managers (npm, pip, cargo), university course registration around prerequisites, and spreadsheet recalculation engines.


B. The vocabulary

6. What is a DAG?

Answer

A directed acyclic graph — directed edges with no circular loops. A prerequisites flowchart.

7. What is in-degree, in plain terms?

Answer

The number of incoming directed edges pointing into a node — the number of uncompleted prerequisites a course has.

8. Why does a cycle make topological ordering impossible?

Answer

Each vertex on the cycle would have to come before itself. Circular reasoning deadlocks.

9. What kind of graph does topological sort require?

Answer

Directed and acyclic. Both conditions — it is meaningless on an undirected graph and impossible with a cycle.


C. Kahn’s algorithm

10. Give Kahn’s algorithm in six steps.

Answer
  1. Compute the in-degree of every vertex.
  2. Push all vertices with in_degree == 0 into a FIFO queue.
  3. Pop u, append it to the order.
  4. For every neighbour v of u, decrement in_degree[v].
  5. If in_degree[v] hits 0, push v.
  6. Repeat until the queue is empty.

11. What does in_degree == 0 mean semantically?

Answer

Every prerequisite of that task is already done, so it is safe to do now.

12. Why does decrementing on the way out model “completing” a task?

Answer

Emitting u means u is finished, so each dependent of u now has one fewer outstanding prerequisite.

13. State the cycle detection guarantee.

Answer

If len(topological_order) < V, a cycle exists. Circular dependencies prevent in-degrees from ever reaching 0, so those vertices never enter the queue.

14. Does Kahn’s algorithm need a separate cycle-detection pass?

Answer

No — the length check is the cycle test, and it costs nothing extra.

15. Kahn’s uses a queue. Does it have to?

Answer

No — any container works, and the choice only changes which valid order you get. A min-heap gives the lexicographically smallest topological order, which is what problems asking for a deterministic answer want.


D. The DFS alternative

16. How does the DFS variant produce a topological order?

Answer

Run DFS and push each vertex onto a list when it finishes; reverse the list at the end. Equivalently, sort by decreasing finish time.

17. Why does decreasing finish time work?

Answer

A vertex finishes only after everything reachable from it has finished, so anything it points to already has a smaller finish time and therefore lands later in the reversed list.

18. How does the DFS variant detect a cycle?

Answer

It looks for a back edge — an edge to a grey (still-open) vertex. A directed graph is a DAG iff DFS produces no back edges. See edge classification.

19. Which variant would you reach for, and why?

Answer

Kahn’s, usually — it is iterative (no recursion limit), the cycle check is a length comparison, and the queue can be swapped for a heap to control ties. The DFS variant is neater when you already need finish times for something else.


E. Costs

20. Time complexity, and why?

Answer

— every vertex is enqueued once and every directed edge is decremented once.

21. Space complexity, and what makes it up?

Answer

— the adjacency list is , plus the in-degree array and queue at .


F. Traps

22. What happens if you flip the edge direction?

Answer

You get the reverse topological order. Be precise about which way dependency points — u → v here means “u must happen before v”.

23. Why must you never assert a single fixed output array in a test?

Answer

Multiple valid orders usually exist. Assert the property instead: for every edge u → v, u appears before v.

24. What is the one check you must always perform?

Answer

len(order) == num_nodes. Without it, a cyclic graph silently returns a partial order that looks plausible.

25. Summarise topological sort in one sentence.

Answer

Repeatedly emit whatever has no remaining prerequisites — , with cycle detection falling out of the count for free.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Graph Algorithms