-
Notifications
You must be signed in to change notification settings - Fork 0
020 — Topological Sort
BFS explored a graph ring by ring, indifferent to any notion of "order" beyond distance. Topological Sort adds a real ordering constraint on top of a graph traversal: given a set of tasks where some must happen before others, produce a valid sequence — and, as a side effect, detect whether such a sequence is even possible at all.
The Graphs chapter covered the data structure itself — nodes and directed edges represented as an adjacency list. This chapter is about recognizing when a graph carries an ordering constraint on top of its connections: an adjacency list plus an inDegree array is what lets you peel off nodes with no remaining prerequisites, one layer at a time.
Picture getting dressed in the morning. You can't put on shoes before socks. You can't button a shirt before putting it on. But you can put on socks and grab your watch in either order — nothing forces one before the other. If you wrote down every "must happen before" rule as an arrow (socks → shoes, shirt → jacket), you'd have a tangle of constraints, but a valid morning routine is just any full ordering of every item that respects every arrow. Crucially: if someone slipped in a broken rule — shoes before socks and socks before shoes — there would be no valid way to get dressed at all. That contradiction is a cycle, and it's the one thing that makes a valid ordering impossible.
Topological Sort is exactly this: turn "must happen before" rules into a directed graph, and produce (or fail to produce) a linear order that respects every one of them.
Topological Sort is a strong reach when the problem statement uses:
-
"Prerequisites" — almost a literal keyword. "Course A requires course B as a prerequisite" is a directed edge
B → A, and "can you complete all courses" is asking whether the resulting graph is acyclic. - "Course schedule" or "build order" — any framing where items depend on other items being finished first, and you need either a valid completion order or a yes/no on whether one exists.
- "Dependencies" in general — package managers resolving install order, task schedulers, spreadsheet cell recalculation order ("cell A depends on cell B") — anywhere "X must come before Y" relationships are given as pairs.
-
"Is it possible to finish all tasks" combined with a list of
(a, b)pairs — this phrasing is the cycle-detection half of the pattern: the answer is "yes" exactly when the dependency graph has no cycle.
The unifying tell: a directed graph of "must come before" relationships, where you need either a valid linear order consistent with every edge, or a detection of whether the constraints are self-contradictory (a cycle).
A dependency graph and the in-degree-driven process that peels off nodes with no remaining prerequisites, one layer at a time (Kahn's algorithm):
socks → shoes
shirt → jacket
shirt → shoes (pretend shirt is also required before shoes)
in-degree: socks=0 shirt=0 shoes=2 jacket=1
queue starts with everything at in-degree 0: [socks, shirt]
process socks → decrement shoes' in-degree (2 → 1)
process shirt → decrement shoes' in-degree (1 → 0), decrement jacket's (1 → 0)
shoes and jacket now both hit in-degree 0 → enqueue both
queue: [shoes, jacket]
process shoes → no outgoing edges
process jacket → no outgoing edges
order produced: socks, shirt, shoes, jacket (or shirt, socks, ... — either is valid)
If instead shoes → socks were ALSO in the graph (a cycle: socks→shoes→socks),
shoes and socks would each perpetually have in-degree ≥ 1 — neither would
ever reach 0, neither would ever enter the queue, and the final order
would be missing nodes. That missing count is exactly how you DETECT a cycle.
func topologicalSortTemplate(nodeCount: Int, edges: [(from: Int, to: Int)]) -> [Int]? {
var adjacency: [[Int]] = Array(repeating: [], count: nodeCount)
var inDegree: [Int] = Array(repeating: 0, count: nodeCount)
for edge in edges {
adjacency[edge.from].append(edge.to)
inDegree[edge.to] += 1
}
var queue: [Int] = (0..<nodeCount).filter { inDegree[$0] == 0 }
var head = 0
var order: [Int] = []
while head < queue.count {
let node = queue[head]
head += 1
order.append(node) // 🔧 Fill in: this IS the topological order, in most problems.
for next in adjacency[node] {
inDegree[next] -= 1
if inDegree[next] == 0 {
queue.append(next)
}
}
}
// 🔧 If fewer nodes made it into `order` than exist, a cycle blocked the rest.
return order.count == nodeCount ? order : nil
}The skeleton never changes: build an adjacency list plus an in-degree count per node, seed a queue with every node that starts at in-degree 0 (no prerequisites), then repeatedly dequeue a node, append it to the answer, and decrement the in-degree of everything it points to — enqueuing any neighbor that just hit 0. The cycle check is free: if the final order doesn't contain every node, whatever's missing was stuck in a cycle (or depended on something stuck in one) and never reached in-degree 0.
Course Schedule — there are numCourses courses labeled 0 to numCourses - 1. prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses.
func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
var adjacency: [[Int]] = Array(repeating: [], count: numCourses)
var inDegree: [Int] = Array(repeating: 0, count: numCourses)
for pair in prerequisites {
let course = pair[0]
let prereq = pair[1]
adjacency[prereq].append(course) // edge: prereq → course
inDegree[course] += 1
}
var queue: [Int] = (0..<numCourses).filter { inDegree[$0] == 0 }
var head = 0
var completed = 0
while head < queue.count {
let course = queue[head]
head += 1
completed += 1
for next in adjacency[course] {
inDegree[next] -= 1
if inDegree[next] == 0 {
queue.append(next)
}
}
}
return completed == numCourses
}
// smoke test
print(canFinish(2, [[1, 0]])) // true — 0 then 1, no conflict
print(canFinish(2, [[1, 0], [0, 1]])) // false — 0 needs 1, 1 needs 0: a cycle
print(canFinish(4, [[1,0],[2,0],[3,1],[3,2]])) // true — a real diamond-shaped dependency graphMapped onto the template: adjacency/inDegree are built identically. Instead of returning the order itself, the problem only needs a yes/no, so completed (a running count) replaces the order array — but it's tracking the exact same thing the template's order.count check does at the end. The edge direction is the one detail worth double-checking per-problem: here prereq → course (not course → prereq), because course b must be processed and removed before course a can ever reach in-degree 0.
Topological Sort is getting dressed in the right order — peel off whatever currently has no unmet prerequisites, and if some items never become peel-able, the rules were contradictory (a cycle) and there's no valid routine.
A problem gives you a list of words and says they're sorted according to some alien language's alphabet — derive that alphabet's letter ordering, or report it's impossible. Explain how you'd construct the graph's edges from adjacent word pairs (what determines an edge between two letters), and why an impossible result here means the same thing structurally as canFinish returning false above.