Medium Topological Sort Advanced Graphs
In plain English: Find an order to take all courses respecting prerequisites, or determine it's impossible.
Kahn's algorithm: compute in-degrees, start with zero in-degree nodes. Process each node by reducing neighbors' in-degrees. If all nodes are processed, we have a valid order; otherwise there's a cycle.
Prompt
Given numCourses and prerequisites pairs [a,b] meaning 'b before a', return a valid course ordering. Return [] if impossible (cycle exists).
Try to write it from scratch before scrolling down.
Solution
from collections import deque, defaultdict
def find_order(num_courses, prerequisites):
# Kahn's algorithm: iteratively remove zero in-degree nodes to build a topological order
graph = defaultdict(list)
in_degree = [0] * num_courses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 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
# course becomes takeable once all its prerequisites are satisfied
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == num_courses else []
# Test: find_order(4, [[1,0],[2,0],[3,1],[3,2]])
# == [0,1,2,3] or [0,2,1,3] (valid topological orders)
# Test: find_order(2, [[0,1],[1,0]]) == [] (cycle)