patternDSA/Topological Sort

Core Pattern → Pattern 27

Topological Sort (Graph)

Order tasks so every dependency comes before its dependent. Impossible if a cycle exists — and the algorithm detects cycles for free. Courses, build systems, package managers — all topo sort.

Frequency:★★★★☆

·~35 min·Intermediate–Hard·7 problems

Prev Two Heaps

The Core Shock

A cycle makes linear ordering impossible. Kahn's algorithm produces the order and detects cycles in the same O(V+E) pass — no extra work.

No cycle (DAG)

Order exists

Every node can be scheduled after all its prerequisites. Kahn's produces one valid order. DFS post-order produces the reverse.

Cycle present

Order impossible

A→B→C→A: no matter where you start, some dependency is unmet. Kahn's detects this: queue empties before all nodes are processed.

The cycle detection is free: after Kahn's finishes, if len(result) < n, some nodes were never dequeued — they're stuck in a cycle with non-zero in-degrees. This single check replaces a separate cycle-detection DFS entirely.

Kahn's (BFS) vs DFS Post-Order

Kahn's is easier to implement. DFS is more elegant but harder to debug.

Kahn's (BFS)

Cycle detection: len(result) < n

Intuitive: process 0-in-degree nodes first

Easy to produce any single valid order

Natural for 'can all tasks complete?' variants

Doesn't give all valid orders without backtracking

Requires in-degree array build upfront

DFS Post-Order

Elegant recursion — often shorter code

Natural for detecting back-edges (cycles via state=1)

Works well for strongly connected component problems

Post-order + reverse = direct topo order

3-state coloring is easy to mis-implement

Recursion depth issues on very large graphs

The 3-Step Framework

Build graph → compute in-degrees → Kahn's BFS → cycle check.

Build the directed graph + in-degree array

Parse prerequisites/edges. Build adjacency list (src → [dests]). Count how many edges point into each node (in-degree). Both take O(E) time and O(V+E) space.

graph = defaultdict(list)
in_degree = [0] * n
for dest, src in prerequisites:
    graph[src].append(dest)
    in_degree[dest] += 1

Edge direction matters. 'A must come before B' means edge A→B. in_degree[B] increments. Always double-check: which node is the prerequisite, which is the dependent.

Kahn's BFS — process in order of readiness

Seed queue with all 0-in-degree nodes. Pop → add to result → for each neighbor, decrement in-degree → if neighbor's in-degree hits 0, enqueue. Result grows one node at a time. Time: O(V+E).

queue = deque(i for i in range(n)
              if in_degree[i] == 0)
while queue:
    node = queue.popleft()
    result.append(node)
    for nb in graph[node]:
        in_degree[nb] -= 1
        if in_degree[nb] == 0:
            queue.append(nb)

The queue at any point holds all nodes whose prerequisites have all been processed. The order within the queue is arbitrary (multiple valid orderings exist) — any valid sequence is acceptable unless the problem asks for lexicographic order, in which case use a min-heap instead of deque.

Cycle check — one line after the BFS

If the result contains all n nodes, the DAG has a valid topological order. If not, some nodes were stuck (their in-degree never reached 0 because they're in a cycle). Return result or [] based on len(result) == n.

return result if len(result) == n else []

# For can-all-tasks-complete:
return len(result) == n   # True/False

# For lexicographic order:
# Use heapq.heappush/heappop instead of deque

This single check replaces an entirely separate cycle-detection algorithm. len(result) < n means some nodes were never processed — they're in a cycle and their in-degrees stayed > 0 throughout the entire BFS.

Pattern Recognition

'prerequisite', 'dependency', 'ordering', 'schedule' → topological sort.

Use Topo Sort When

"Can you finish all courses?" — cycle check

Return order to complete tasks with prerequisites

Alien Dictionary — infer character ordering

All valid orderings — backtracking on Kahn's

Reconstruct sequence — unique supersequence check

Minimum Height Trees — peel leaves inward

"Find build order" in any dependency graph

Detect deadlocks in concurrent systems

Common Pitfalls

Edge direction reversed: dest→src instead of src→dest

In-degree of src incremented instead of dest

Not seeding all 0-in-degree nodes (seeding only node 0)

Returning result without cycle check (len check missing)

Alien Dict: not checking prefix invalidity (longer word first)

Alien Dict: adding duplicate edges → over-counting in-degree

DFS: using True/False visited instead of 3-state (misses cycles)

All Orders: forgetting to restore in-degrees when backtracking

On this page