PATTERN 0 OF 22

Topological Sort

Order nodes in a directed acyclic graph (DAG) so every edge points forward. Master cycle detection, Kahn's algorithm (BFS), and DFS post-order reversal for dependency ordering, course scheduling, and alien dictionaries.

Time: O(V + E) where V = vertices and E = edges

Space: O(V + E) for adjacency list, in-degree array, and queue

Learn & Reference

Understanding the Pattern

Topological Sort Pattern

A topological sort produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before v in the ordering. If the graph has a cycle, no valid topological ordering exists.

Core Concept

Think of it like course prerequisites: if Course A requires Course B, then B must appear before A in any valid schedule. Topological sort finds such a schedule — or detects that one is impossible (a cycle exists).

Prerequisites:              Topological Order:
0 → 1 → 3                  [0, 2, 1, 3] or [2, 0, 1, 3]
2 → 1

A DAG can have multiple valid topological orderings. Any ordering where all edges point "forward" is correct.

Key Techniques

1. Kahn's Algorithm (BFS with In-Degrees)

The most intuitive approach. Track the in-degree (number of incoming edges) of each node. Nodes with in-degree 0 have no unsatisfied dependencies and can go first.

1. Build adjacency list and compute in-degree for each node
2. Add all nodes with in-degree 0 to a queue
3. While queue is not empty:
   a. Remove node from queue → add to result
   b. For each neighbor, decrement its in-degree
   c. If neighbor's in-degree becomes 0, add to queue
4. If result has all nodes → valid ordering
   If result is shorter → cycle exists

2. DFS Post-Order Reversal

Process nodes in DFS order, and add each node to the result after all its descendants are processed (post-order). Reverse the result to get topological order.

1. For each unvisited node, run DFS
2. In DFS, mark node as "in progress" (on current path)
3. Recurse on all neighbors
4. If we visit an "in progress" node → cycle detected
5. After all neighbors done, mark as "done" and push to stack
6. Pop all from stack → topological order

3. Cycle Detection

Both approaches naturally detect cycles:

Kahn's: If the result has fewer nodes than the graph, a cycle exists (some nodes never reached in-degree 0)
DFS: If we encounter a node that's currently "in progress" on the recursion stack, we've found a back edge (cycle)

4. Building the Graph from Constraints

Many problems don't give you an explicit graph — you derive edges from constraints:

Course prerequisites: [course, prereq] → edge from prereq to course
Alien dictionary: Compare adjacent words to find character ordering → edges between characters

Common Mistakes

Forgetting to handle disconnected components — In Kahn's algorithm, initialize ALL nodes with in-degree 0 into the queue (not just node 0). In DFS, iterate over ALL nodes.
Wrong edge direction — For prerequisites [a, b] meaning "b before a," the edge is b → a, not a → b. Getting this backwards produces the reverse ordering.
Not detecting cycles — Always check if the result includes all nodes. Returning a partial ordering when a cycle exists is a common source of wrong answers.
Confusing "visited" states in DFS — You need THREE states: unvisited, in-progress (on current recursion path), and done. Using only two states (visited/unvisited) can't detect cycles.
Missing characters in Alien Dictionary — Characters that appear in words but have no ordering constraints still need to be included in the result. Track all unique characters from the input.

When to Use

The problem involves **ordering with dependencies** (prerequisites, build order, task scheduling)

You need to detect if a **dependency graph has a cycle**

The problem asks for a valid **sequence where constraints are satisfied**

You need to derive an **ordering from pairwise comparisons** (alien dictionary, custom sort)

The problem mentions **directed acyclic graph (DAG)** or topological ordering

Template

1# Kahn's Algorithm — Topological Sort (BFS)
2from collections import deque
3
4def topo_sort(num_courses, prerequisites):
5    graph = [[] for _ in range(num_courses)]
6    in_degree = [0] * num_courses
7
8    for course, prereq in prerequisites:
9        graph[prereq].append(course)
10        in_degree[course] += 1
11
12    queue = deque(i for i in range(num_courses) if in_degree[i] == 0)
13    order = []
14
15    while queue:
16        node = queue.popleft()
17        order.append(node)
18        for neighbor in graph[node]:
19            in_degree[neighbor] -= 1
20            if in_degree[neighbor] == 0:
21                queue.append(neighbor)
22
23    return order if len(order) == num_courses else []

{ }

Syntax Reference

1# Build adjacency list + in-degree array
2from collections import deque, defaultdict
3
4graph = defaultdict(list)  # node -> [neighbors]
5in_degree = [0] * num_nodes
6
7for src, dst in edges:
8    graph[src].append(dst)
9    in_degree[dst] += 1
10
11# Kahn's: initialize queue with in-degree 0 nodes
12queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
13
14# Process
15while queue:
16    node = queue.popleft()
17    for neighbor in graph[node]:
18        in_degree[neighbor] -= 1
19        if in_degree[neighbor] == 0:
20            queue.append(neighbor)

📋

Common Recipes

1# Recipe 1: Kahn's Algorithm — Topological Sort (BFS)
2from collections import deque, defaultdict
3
4def topo_sort_kahn(num_nodes, edges):
5    graph = defaultdict(list)
6    in_degree = [0] * num_nodes
7    for src, dst in edges:
8        graph[src].append(dst)
9        in_degree[dst] += 1
10
11    queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
12    order = []
13
14    while queue:
15        node = queue.popleft()
16        order.append(node)
17        for neighbor in graph[node]:
18            in_degree[neighbor] -= 1
19            if in_degree[neighbor] == 0:
20                queue.append(neighbor)
21
22    return order if len(order) == num_nodes else []  # empty = cycle
23
24# Recipe 2: DFS Post-Order — Topological Sort
25def topo_sort_dfs(num_nodes, edges):
26    graph = defaultdict(list)
27    for src, dst in edges:
28        graph[src].append(dst)
29
30    WHITE, GRAY, BLACK = 0, 1, 2
31    color = [WHITE] * num_nodes
32    order = []
33    has_cycle = False
34
35    def dfs(node):
36        nonlocal has_cycle
37        if has_cycle:
38            return
39        color[node] = GRAY
40        for neighbor in graph[node]:
41            if color[neighbor] == GRAY:
42                has_cycle = True
43                return
44            if color[neighbor] == WHITE:
45                dfs(neighbor)
46        color[node] = BLACK
47        order.append(node)
48
49    for i in range(num_nodes):
50        if color[i] == WHITE:
51            dfs(i)
52
53    return order[::-1] if not has_cycle else []
54
55# Recipe 3: Cycle Detection (Kahn's shortcut)
56def has_cycle(num_nodes, edges):
57    graph = defaultdict(list)
58    in_degree = [0] * num_nodes
59    for src, dst in edges:
60        graph[src].append(dst)
61        in_degree[dst] += 1
62    queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
63    count = 0
64    while queue:
65        node = queue.popleft()
66        count += 1
67        for neighbor in graph[node]:
68            in_degree[neighbor] -= 1
69            if in_degree[neighbor] == 0:
70                queue.append(neighbor)
71    return count != num_nodes  # True if cycle exists

O(n)

Complexity

Operation	Time	Space	Notes
Kahn's Algorithm (BFS)	O(V + E)	O(V + E)	Adjacency list + in-degree array + queue
DFS Post-Order	O(V + E)	O(V + E)	Adjacency list + color array + recursion stack
Cycle Detection	O(V + E)	O(V + E)	Same as topo sort — cycle = incomplete ordering
Build graph from edges	O(E)	O(V + E)	One pass to build adjacency list + in-degrees

Watch Out

✗Forgetting to handle disconnected components — In Kahn's algorithm, initialize ALL nodes with in-degree 0 into the queue (not just node 0). In DFS, iterate over ALL nodes.
✗Wrong edge direction — For prerequisites `[a, b]` meaning "b before a," the edge is `b → a`, not `a → b`. Getting this backwards produces the reverse ordering.
✗Not detecting cycles — Always check if the result includes all nodes. Returning a partial ordering when a cycle exists is a common source of wrong answers.
✗Confusing "visited" states in DFS — You need THREE states: unvisited, in-progress (on current recursion path), and done. Using only two states (visited/unvisited) can't detect cycles.
✗Missing characters in Alien Dictionary — Characters that appear in words but have no ordering constraints still need to be included in the result. Track all unique characters from the input.

PRACTICE PROBLEMS

Hash Maps