DSA · Chapter 27 of 40
Topological Sort
A topological sort orders the vertices of a directed acyclic graph so that every edge points forward. It answers 'in what order can these dependent tasks run?' — course prerequisites, build systems and job scheduling.
Kahn's algorithm repeatedly removes vertices with in-degree zero; if any vertices remain at the end, the graph has a cycle.
Kahn's algorithm
Compute in-degrees, enqueue all zero-degree vertices, and each time you pop one, decrement its neighbours and enqueue any that reach zero.
DFS version
Run DFS and push each vertex onto a stack after all its descendants are processed; reversing that stack gives a topological order.
Example 1 (python)
from collections import deque
def topo(graph):
indeg = {v: 0 for v in graph}
for v in graph:
for n in graph[v]:
indeg[n] += 1
q = deque([v for v in indeg if indeg[v] == 0])
out = []
while q:
v = q.popleft()
out.append(v)
for n in graph[v]:
indeg[n] -= 1
if indeg[n] == 0:
q.append(n)
return out if len(out) == len(graph) else []
print(topo(graph))Output
['A', 'B', 'C', 'D']An empty result means the graph had a cycle.
Example 2 (python)
courses = {'math': [], 'physics': ['math'], 'eng': ['physics']}
# edges point prerequisite -> course
graph2 = {'math': ['physics'], 'physics': ['eng'], 'eng': []}
print(topo(graph2))Output
['math', 'physics', 'eng']Course scheduling is the classic topological sort question.
Key points
- Topological sort works only on directed acyclic graphs.
- Kahn's algorithm uses in-degrees and a queue.
- A leftover vertex means a cycle exists.
- Complexity is O(V + E).
💡 Note: 'Course schedule' and 'build order' questions are topological sort in disguise.