Topological Sort

Kahn's algorithm

A topological order lists nodes of a directed acyclic graph so every edge points forward: courses after their prerequisites, build steps after dependencies. Kahn's algorithm repeatedly takes nodes with in-degree zero, removing their outgoing edges. If some nodes are never processed, the graph has a cycle and no valid order exists. DFS with post-order is the alternative.

Ordering courses and detecting a cycle, run

I ran this with Python 3.12.3 (standard library only). Four courses get a valid order; two courses that require each other return an empty list.

# Topological sort (Kahn's algorithm): course prerequisites
from collections import deque

def course_order(n, prereqs):
    graph, indeg = [[] for _ in range(n)], [0] * n
    for course, pre in prereqs:
        graph[pre].append(course)
        indeg[course] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return order if len(order) == n else []   # empty: a cycle exists

print(course_order(4, [(1, 0), (2, 0), (3, 1), (3, 2)]))
print(course_order(2, [(1, 0), (0, 1)]))

Output:

[0, 1, 2, 3]
[]

Get the edge direction right

Decide clearly whether an edge means "prerequisite to course" or the reverse; mixing them is the common bug.

त्वरित जाँच: How does Kahn's algorithm detect a cycle?

• Not all nodes get processed because some never reach in-degree zero
• The queue overflows
• A node is visited twice
• The graph has more edges than nodes