Topological Sort
Topological sort orders nodes in a directed graph so that for every edge A → B, A comes before B. Think course prerequisites, build dependencies, or any "do this before that" scenario.
The Core Idea
Only works on Directed Acyclic Graphs (DAGs) - if there's a cycle, there's no valid ordering. The algorithm repeatedly finds nodes with no incoming edges, adds them to the result, and removes their outgoing edges.
If a valid topological ordering exists, the graph has no cycles. If you can't complete the sort (some nodes always have incoming edges), there's a cycle - and no valid ordering is possible.
Kahn's Algorithm (BFS)
from collections import deque
def topologicalSort(numNodes, edges):
# Build graph and count incoming edges
graph = [[] for _ in range(numNodes)]
indegree = [0] * numNodes
for src, dst in edges:
graph[src].append(dst)
indegree[dst] += 1
# Start with nodes that have no prerequisites
queue = deque([i for i in range(numNodes) if indegree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
# If we couldn't process all nodes, there's a cycle
return result if len(result) == numNodes else []Classic: Course Schedule
Can you finish all courses given prerequisites?
def canFinish(numCourses, prerequisites):
order = topologicalSort(numCourses, prerequisites)
return len(order) == numCoursesWhen to Use Topological Sort
- Course scheduling - Prerequisites determine order
- Build systems - Compile dependencies first
- Task scheduling - Some tasks depend on others
- Cycle detection - In directed graphs
- Finding execution order - Any DAG ordering problem
Kahn's algorithm (BFS with indegree) is shown above. DFS-based topological sort reverses the post-order - process node after all descendants are done.