Pattern 21 of 27

Topological Sort

Order the nodes of a directed graph so every edge points forward, and detect a cycle when no such order exists.

Cost: O(V + E) time and space
Problems: 6

When to reach for it

Tasks have prerequisites or dependencies.
The prompt asks for a valid order, or whether any valid order exists.
The graph is directed and a cycle would make the task impossible.

How it works

Kahn's algorithm counts incoming edges for every node and seeds a queue with the nodes that have none. Taking a node from the queue means it is safe to do now, so its outgoing edges are removed, and any neighbour whose count reaches zero joins the queue. If fewer nodes come out than the graph contains, the rest are stuck in a cycle. A DFS that tracks the nodes on its current path detects cycles in the same situations.

The template

Written for Course Schedule (write-up)

from collections import deque

def can_finish(num_courses, prerequisites):
    indegree = [0] * num_courses
    adj = [[] for _ in range(num_courses)]
    for course, pre in prerequisites:
        adj[pre].append(course)
        indegree[course] += 1
    queue = deque(i for i in range(num_courses) if indegree[i] == 0)
    taken = 0
    while queue:
        u = queue.popleft()
        taken += 1
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    return taken == num_courses       # fewer means a cycle

Open in the editor Trace it line by line

Six problems, in learning order

1.Course ScheduleLeetCode 207Possible only if every course leaves the queue.Medium
2.Course Schedule IILeetCode 210Record the order in which nodes leave the queue.Medium
3.Find Eventual Safe StatesLeetCode 802Reverse the edges; the safe nodes are those topological sort reaches from terminal nodes.Medium
4.Course Schedule IVLeetCode 1462Pass reachability sets along the topological order.Not in the curated 370 yet.Medium
5.Sort Items by Groups Respecting DependenciesLeetCode 1203Two layers of topological sort: groups first, then items inside each group.Not in the curated 370 yet.Hard
6.Find All Possible Recipes from Given SuppliesLeetCode 2115Supplies start with nothing pending; a recipe becomes makeable once all its ingredients are.Not in the curated 370 yet.Medium

What usually goes wrong

Reversing edge direction: the pair [course, prerequisite] means the prerequisite comes first.
Applying it to an undirected graph.
Assuming the order is unique when the question accepts any valid order.