7.29

Model each course as a vertex in a directed graph and every prerequisite pair (x, y) as a directed edge x → y. A student can finish the program iff this graph is a Directed Acyclic Graph (DAG), i.e. it admits a topological order. Detect cycles (and simultaneously produce that order) with Kahn’s algorithm:

in_deg = [0]*n # indegree of every vertex
for (x,y) in prereq: # build indegree list
   in_deg[y] += 1

Q = [v for v in 0..n-1 if in_deg[v]==0] # sources
order = []
while Q: # remove sources repeatedly
   v = Q.pop()
   order.append(v)
   for u in adj[v]:
      in_deg[u] -= 1
      if in_deg[u] == 0: Q.append(u)

if len(order) == n:
   print("Possible – topological order is", order)
else:
   print("Impossible – a prerequisite cycle exists")

The algorithm runs in O(n + m) time and O(n) space, where m is the number of prerequisite pairs. If a cycle is found, the program’s requirements are inconsistent; otherwise, the produced order tells how any student can schedule the courses.

Back to Chapter 7