What is Topological Sort and How Does Kahn's Algorithm Work?
Understand topological sort and how Kahn's in-degree BFS algorithm orders a DAG and detects cycles, with Python code.
Expected Interview Answer
Topological sort orders the vertices of a directed acyclic graph so that every edge points from an earlier vertex to a later one, and Kahn's algorithm produces this order by repeatedly removing vertices whose in-degree (number of incoming edges) has dropped to zero, meaning all their prerequisites are already satisfied.
Kahn's algorithm first computes the in-degree of every vertex, then places every vertex with in-degree zero into a queue since they have no unmet prerequisites. It repeatedly dequeues a vertex, appends it to the result order, and decrements the in-degree of each of its neighbors; any neighbor whose in-degree drops to zero is enqueued next. If the algorithm finishes with fewer vertices in the output than the graph actually has, the remaining vertices form a cycle and no valid topological order exists — this doubles as a cycle-detection check. It runs in O(V + E) time and is the standard technique behind build systems, course-prerequisite scheduling, and package dependency resolution.
- O(V + E) time using a simple queue and in-degree counts
- Naturally detects cycles as a byproduct (incomplete output means a cycle)
- Iterative, avoiding recursion depth limits that DFS-based topo sort risks
- Directly used by build systems and dependency resolvers
AI Mentor Explanation
A coaching academy schedules skill certifications so every prerequisite skill is certified before the skill that depends on it. Kahn's approach starts by certifying every skill that has zero prerequisites left unmet, then for each certified skill, it checks all skills that depended on it and marks one prerequisite as satisfied; any skill whose prerequisites just hit zero joins the certification queue next. If skills remain uncertified at the end because their prerequisite counts never hit zero, those skills depend on each other in a loop and can never actually be scheduled. This zero-prerequisite queue is exactly Kahn's in-degree-based topological sort.
Step-by-Step Explanation
Step 1
Compute in-degrees
Count incoming edges for every vertex across the whole graph.
Step 2
Seed the queue
Enqueue every vertex whose in-degree is already zero.
Step 3
Process and decrement
Dequeue a vertex, append to output, decrement in-degree of each neighbor.
Step 4
Enqueue newly-freed vertices
Any neighbor whose in-degree hits zero is enqueued; if the output ends short of V vertices, a cycle exists.
What Interviewer Expects
- Explain the in-degree / zero-prerequisite intuition clearly
- State the O(V + E) time complexity
- Explain how the algorithm detects a cycle (output length < V)
- Give a real use case: build systems, course scheduling, package resolution
Common Mistakes
- Confusing Kahn's algorithm (BFS/queue-based) with the DFS-plus-stack approach to topological sort
- Forgetting to check whether the output includes all vertices, missing the cycle-detection step
- Not decrementing in-degrees correctly when a vertex has multiple edges to the same neighbor
- Assuming topological sort produces a unique order (it is often not unique)
Best Answer (HR Friendly)
“Topological sort orders tasks so every task comes after everything it depends on, which is why it is the standard approach for scheduling problems. Kahn's algorithm does this by first working on all the tasks with no dependencies left, then repeatedly freeing up new tasks as their dependencies get completed, which also naturally reveals if there is a circular dependency that can never be resolved.”
Code Example
from collections import deque
def topological_sort(graph, num_vertices):
in_degree = {v: 0 for v in graph}
for node in graph:
for neighbor in graph[node]:
in_degree[neighbor] += 1
queue = deque([v for v in in_degree if in_degree[v] == 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_vertices:
raise ValueError("Graph has a cycle; no valid topological order")
return orderFollow-up Questions
- How would you implement topological sort with DFS and a stack instead?
- How would you detect the cycle vertices specifically, not just that one exists?
- How would you find all valid topological orderings, not just one?
- How does topological sort relate to critical path scheduling in project management?
MCQ Practice
1. In Kahn's algorithm, which vertices are enqueued first?
Vertices with in-degree zero have no unmet prerequisites, so they can be processed immediately.
2. How does Kahn's algorithm detect a cycle?
Vertices stuck in a cycle never reach in-degree zero, so they never get enqueued or added to the output.
3. What is the time complexity of Kahn's algorithm?
Each vertex is dequeued once and each edge is examined once when decrementing in-degrees, giving O(V + E).
Flash Cards
What does Kahn's algorithm use to decide processing order? — Vertex in-degree — vertices with zero incoming edges go first.
How does Kahn's algorithm detect a cycle? — If the final output has fewer vertices than the graph, the rest form a cycle.
What data structure drives Kahn's algorithm? — A queue (or any FIFO structure) of vertices with in-degree zero.
Name a real-world use of topological sort. — Build systems, package dependency resolution, or course prerequisite scheduling.