What is Topological Sort?
Learn topological sort with Kahn’s algorithm, a Python code example, cycle detection, and real-world build system uses.
Expected Interview Answer
Topological sort produces a linear ordering of the nodes in a directed acyclic graph such that for every directed edge from node A to node B, A appears before B in the ordering.
It only works on directed acyclic graphs, since a cycle would create a contradictory ordering requirement. The two standard approaches are Kahn’s algorithm, which repeatedly removes nodes with zero in-degree using a queue, and depth-first search, which pushes nodes onto a stack after all their descendants have been visited and then reverses the stack. Both run in O(V + E) time. Topological sort is the algorithm behind build systems, task scheduling with dependencies, and course-prerequisite ordering, anywhere a partial order of dependencies must be flattened into a valid execution sequence.
- Produces a valid dependency-respecting execution order
- Runs in O(V + E) linear time
- Detects cycles as a side effect when no valid ordering exists
- Foundation for build systems, task schedulers, and compilers
AI Mentor Explanation
A cricket academy sequencing its coaching curriculum must teach the forward defensive stroke before the cover drive, and basic footwork before either, since each skill depends on the ones before it — teaching them out of order leaves gaps. Topological sort formalizes exactly this: given a set of prerequisite dependencies as a directed graph, it produces one valid order where every skill appears after everything it depends on.
Step-by-Step Explanation
Step 1
Confirm the graph is a DAG
Topological sort is undefined for graphs with cycles, since a cycle has no valid linear ordering.
Step 2
Compute in-degrees (Kahn’s algorithm)
Count incoming edges for every node and initialize a queue with all zero-in-degree nodes.
Step 3
Repeatedly remove zero-in-degree nodes
Dequeue a node, add it to the result, and decrement the in-degree of its neighbors, enqueuing any that reach zero.
Step 4
Detect cycles
If the result list has fewer nodes than the graph after processing, a cycle exists and no valid ordering is possible.
What Interviewer Expects
- Recognizing that topological sort requires a directed acyclic graph
- Explaining at least one algorithm (Kahn’s BFS-based or DFS-based)
- Stating the O(V + E) time complexity
- Connecting the concept to real applications like build systems or course prerequisites
Common Mistakes
- Attempting topological sort on a graph that contains a cycle
- Forgetting to reverse the stack in the DFS-based approach
- Confusing topological sort with a regular graph traversal order
- Not handling disconnected components in the graph
Best Answer (HR Friendly)
“Topological sort takes a set of tasks with dependencies, like course prerequisites, and produces one valid order to complete them where nothing comes before something it depends on. It only works when there are no circular dependencies, and it is the algorithm behind build systems and task schedulers that need to figure out a safe execution order automatically.”
Code Example
from collections import deque, defaultdict
def topological_sort(num_nodes, edges):
graph = defaultdict(list)
in_degree = [0] * num_nodes
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(n for n in range(num_nodes) if in_degree[n] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(order) != num_nodes:
raise ValueError("Graph has a cycle; no valid topological order")
return orderFollow-up Questions
- How does Kahn’s algorithm differ from the DFS-based approach to topological sort?
- How would you detect a cycle in a directed graph using topological sort?
- What is the time complexity of topological sort and why?
- How does topological sort apply to resolving package or module dependencies?
MCQ Practice
1. Topological sort is only defined for which type of graph?
A cycle would make a consistent linear ordering impossible, so topological sort requires a DAG.
2. In Kahn’s algorithm, which nodes are added to the queue initially?
Nodes with zero in-degree have no unresolved dependencies and can be processed first.
3. What is the time complexity of topological sort using Kahn’s algorithm?
Each node and edge is processed a constant number of times, giving linear O(V + E) time.
Flash Cards
Topological sort — A linear ordering of DAG nodes where every edge points from an earlier node to a later one.
Kahn’s algorithm — BFS-based topological sort using in-degree counts and a queue of zero-in-degree nodes.
DFS-based topological sort — Push nodes onto a stack after visiting all descendants, then reverse the stack.
Cycle detection — If fewer nodes are ordered than exist in the graph, a cycle exists and no valid order is possible.