Medium Topological Sort Advanced Graphs
In plain English: Order tasks so that every task comes after its prerequisites, using a queue-based approach.
Start with nodes having no prerequisites (in-degree 0). Process them, reduce neighbors' in-degrees, and add newly zero-degree nodes to the queue.
Prompt
Given a directed acyclic graph (DAG) as an adjacency list, return a topological ordering of its nodes using Kahn's algorithm (BFS-based).
Try to write it from scratch before scrolling down.
Solution
from collections import deque
def topological_sort(graph, n):
in_deg = [0] * n
for u in range(n):
for v in graph.get(u, []):
in_deg[v] += 1
# seed queue with nodes that have no incoming edges (ready to process)
q = deque(i for i in range(n) if in_deg[i] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in graph.get(u, []):
in_deg[v] -= 1
# neighbour becomes processable once all its prerequisites are done
if in_deg[v] == 0:
q.append(v)
return order if len(order) == n else [] # empty if cycle
# Test: {0:[1,2], 1:[3], 2:[3], 3:[]}, n=4 => [0,1,2,3] or [0,2,1,3]