Topological Sort

Question 1

Topological Sort is only possible for which type of graph?

Accepted Answer

Directed Acyclic Graph — If a graph has a cycle, there is no valid linear ordering because dependencies would be circular. DAG is required.

Question 2

A topological sort produces…

Accepted Answer

A linear order where u always precedes v — It orders vertices so that all dependency edges point forward — used to sequence tasks that depend on one another.

Question 3

How many valid topological orderings can a DAG with no ordering constraints between nodes have?

Accepted Answer

Factorial of the number of nodes (n!) — If no edges exist between a set of n nodes, any permutation is valid, giving up to n! orderings. In practice most DAGs have fewer due to edges constraining the order.

Question 4

Kahn's algorithm builds a topological order using…

Accepted Answer

Repeatedly removing zero-in-degree vertices — Start with all in-degree-0 vertices; remove one, decrement its neighbors' in-degrees, and enqueue any that hit 0 — emitting a valid order.

Question 5

The DFS-based topological sort outputs vertices in…

Accepted Answer

Reverse of DFS finish time — Pushing each vertex onto a stack when its DFS finishes, then reversing, yields a topological order.

Question 6

How does Kahn's algorithm detect a cycle?

Accepted Answer

Fewer than V vertices output — Vertices in a cycle never reach in-degree 0, so they're never emitted; if the output has < V vertices, a cycle exists.

Question 7

What is the time complexity of topological sort?

Accepted Answer

O(V + E) — Both Kahn's and DFS-based variants process each vertex and edge once: O(V + E).

Question 8

Is a topological order unique?

Accepted Answer

No, multiple valid orderings can exist in the same graph — Whenever multiple vertices have in-degree 0 simultaneously, any can come next, so several valid orders may exist.

Question 9

A classic application of topological sort is…

Accepted Answer

Build systems and task scheduling workflows — Compiling files, scheduling courses, and resolving package dependencies all need a valid order respecting prerequisite edges.

Question 10

To get the LEXICOGRAPHICALLY smallest topological order, modify Kahn's to use a…

Accepted Answer

Min-heap — Replacing the queue with a min-heap always emits the smallest available vertex next, producing the lexicographically smallest valid order in O((V+E) log V).

Topological Sort (Kahn's Algorithm)

Kahn’s algorithm

Test your knowledge

Topological Sort is only possible for which type of graph?

Write the code

Course Schedule II

Example Cases

The short version

In more depth

Order of Operations

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?