What Problem Does It Solve?
Some tasks have hard dependencies: you cannot start task B until task A is complete. Topological Sort takes a set of such dependencies and produces a valid linear ordering — a sequence where every task appears after all of its prerequisites.
This pattern appears in: build systems (compile A before linking B), course scheduling, package dependency resolution, and CI/CD pipeline ordering.
The Data Structure: Directed Acyclic Graph (DAG)
Dependencies are modeled as a Directed Acyclic Graph (DAG):
- Directed: edges have a direction (A → B means "A must come before B").
- Acyclic: no cycles. If A depends on B and B depends on A, there is no valid ordering — this is a deadlock or circular dependency, and Topological Sort detects it.
Kahn's Algorithm (BFS-Based)
Kahn's algorithm uses the concept of in-degree: the number of incoming edges a node has (i.e., how many prerequisites it has).
Courses: 0→1, 0→2, 1→3, 2→3
In-degrees: {0:0, 1:1, 2:1, 3:2}
Step 1: Queue all nodes with in-degree 0 → Queue: [0]
Step 2: Process 0. Order: [0]. Decrement neighbors 1 and 2.
In-degrees: {1:0, 2:0, 3:2}. Queue: [1, 2]
Step 3: Process 1. Order: [0,1]. Decrement neighbor 3.
In-degrees: {3:1}. Queue: [2]
Step 4: Process 2. Order: [0,1,2]. Decrement neighbor 3.
In-degrees: {3:0}. Queue: [3]
Step 5: Process 3. Order: [0,1,2,3]. Done.
from collections import deque
def topo_sort(num_courses, prerequisites):
in_degree = [0] * num_courses
graph = [[] for _ in range(num_courses)]
for dest, src in prerequisites:
graph[src].append(dest)
in_degree[dest] += 1
queue = deque([i for i in range(num_courses) if in_degree[i] == 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 not all nodes processed, a cycle exists
return order if len(order) == num_courses else []
print(topo_sort(4, [[1,0],[2,0],[3,1],[3,2]]))
# Output: [0, 1, 2, 3] (or [0, 2, 1, 3] — multiple valid orderings exist)
Cycle Detection
If the algorithm finishes and len(order) < num_courses, some nodes still have in_degree > 0 — they are part of a cycle and were never added to the queue. This is how Topological Sort doubles as a cycle detector in directed graphs.