Module A-8 — Topological Sort: Kahn's Algorithm and DFS-Based Ordering
What this module covers: Given a set of tasks with dependencies — task B can't run until task A finishes — what's a valid order to run all of them? This module covers two different ways to answer that question: Kahn's algorithm, built on Module F-7's queue and Module P-6's in-degree concept, and a DFS-based approach (Module A-4) that arrives at the same answer from the opposite direction. Both double as cycle detectors: no valid order exists if the dependencies contain a cycle.
The Problem: Ordering a DAG
A topological sort is a linear ordering of a directed graph's nodes such that for every edge u → v, u appears before v in the ordering. This only makes sense on a directed acyclic graph (DAG) — Module P-6 already flagged that this requires directionality; a cycle makes the question unanswerable, since a cycle A → B → A would require A before B and B before A simultaneously.
Kahn's Algorithm: Start With What Has No Prerequisites
Kahn's algorithm is structurally a BFS (Module A-5): repeatedly process nodes with no remaining unprocessed dependencies, using Module P-6's in-degree (number of incoming edges) to track exactly that.
typescript
Every node starting with in-degree 0 has no unmet dependency — it's safe to run first. Processing it "removes" its outgoing edges by decrementing each neighbor's in-degree, and any neighbor whose in-degree just hit zero has had its last remaining prerequisite satisfied, making it newly eligible. This is precisely BFS's layer-by-layer discipline (Module A-5), just measuring "layer" by dependency depth rather than hop distance from a single start node. The cycle check is built directly into the completion condition: if a cycle exists, every node inside it permanently retains an in-degree above zero (each depends on another node in the same cycle, which can never be fully "satisfied" first), so those nodes never enter the queue at all — the final order comes up short, and the length mismatch is the detection signal.
DFS-Based Topological Sort: Postorder, Then Reverse
A different route to the same answer, built on Module A-4's DFS and Module P-4's postorder traversal: run DFS, and every time a node finishes being explored (everything reachable from it — every node that depends on it — has been fully processed) push it onto a result list — then reverse that list at the end.
typescript
Why postorder-then-reverse works: with the convention that an edge u → v means "u must come before v," a node's outgoing edges point to the things that depend on it, not to its dependencies. dfs(node) recurses into those dependents first, so each of them finishes and gets pushed onto resultbeforenode itself does. That means in the raw result list, a node's dependents end up appearing before it — exactly backwards from what a valid topological order requires (a prerequisite must come before whatever depends on it). Reversing the whole list flips this, putting every prerequisite before its dependents, which is the correct final order. The inProgress set is the cycle detector: it tracks nodes currently "open" on the active DFS path, and reaching a node that's still open (not yet finished) means the current path has looped back on itself — a cycle, structurally distinct from simply reaching an already-visited (fully finished, safe) node from a different branch.
Where This Shows Up in Your Stack
npm/package manager dependency resolution: determining a valid install/build order when package A depends on B, which depends on C, is a direct topological sort over the dependency graph — and a circular dependency (A depends on B depends on A) is exactly the cycle case both algorithms above detect and reject.
Build tools and task runners (Makefiles, Webpack/Turbopack's internal module graphs, CI/CD pipeline stage definitions with explicit dependsOn relationships) all need a valid execution order respecting declared dependencies — the same problem, applied to build targets or pipeline stages instead of npm packages.
Spreadsheet formula recalculation: if cell C depends on cell B which depends on cell A, recalculating in the correct order (A, then B, then C) after any single cell changes is a topological sort over the cell-dependency graph — and a formula that creates a circular reference (a genuine, common spreadsheet error) is precisely the cycle case this module's algorithms detect.
Course prerequisite scheduling (the canonical textbook framing of this problem) — determining a valid sequence of courses given prerequisite requirements, and detecting an impossible prerequisite cycle — maps onto this module's algorithms with no translation needed at all.
Summary
Topological sort orders a DAG's nodes so every edge points from earlier to later in the ordering — meaningless on a graph containing a cycle, since a cycle would require contradictory orderings.
Kahn's algorithm is BFS driven by in-degree (Module P-6): start with zero-in-degree nodes, process them, decrement neighbors' in-degree, and enqueue any that reach zero — a cycle is detected when the final order comes up short of every node.
DFS-based topological sort uses postorder (Module P-4): push a node only after all its dependencies have been fully explored, then reverse the whole result — a cycle is detected via an inProgress set tracking nodes still open on the current DFS path.
Both algorithms answer the identical question from opposite directions — Kahn's builds the order forward from "no dependencies," DFS builds it backward from "fully resolved," relying on the reversal to correct the direction.
This is the literal mechanism behind dependency resolution in package managers, build tools, spreadsheet recalculation, and prerequisite scheduling — anywhere "valid order given dependencies" is the actual question.
The next module, Grid Traversal Patterns: Flood Fill and Multi-Source BFS, formalizes the grid-as-implicit-graph framing used informally in Modules A-4 and A-5 — and extends BFS to start from multiple sources simultaneously.
Knowledge Check
In topologicalSortKahn, why does a node whose in-degree never reaches zero indicate that the graph contains a cycle?
In topologicalSortDFS, why must the result list be reversed after collecting nodes in postorder, rather than used directly in that order?
What specific role does the inProgress set play in topologicalSortDFS's cycle detection, and how does it differ from simply checking visited?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functiontopologicalSortKahn(graph: Map<string,string[]>):string[]|null{const inDegree =newMap<string,number>();// Initialize every node's in-degree to 0, then count actual incoming edgesfor(const node of graph.keys()) inDegree.set(node,0);for(const neighbors of graph.values()){for(const neighbor of neighbors){ inDegree.set(neighbor,(inDegree.get(neighbor)??0)+1);}}// Start with every node that has NO prerequisites at allconst queue:string[]=[];for(const[node, degree]of inDegree){if(degree ===0) queue.push(node);}const order:string[]=[];while(queue.length >0){const node = queue.shift()!;// Module F-7 order.push(node);for(const neighbor of graph.get(node)??[]){ inDegree.set(neighbor, inDegree.get(neighbor)!-1);// one of this neighbor's prerequisites is now satisfiedif(inDegree.get(neighbor)===0) queue.push(neighbor);// all its prerequisites are now satisfied}}// If not every node made it into the order, some nodes' in-degree never hit zero — a cyclereturn order.length === inDegree.size ? order :null;}
functiontopologicalSortDFS(graph: Map<string,string[]>):string[]|null{const visited =newSet<string>();const inProgress =newSet<string>();// nodes currently on the current DFS path — detects back-edgesconst result:string[]=[];let hasCycle =false;functiondfs(node:string):void{if(hasCycle)return;if(inProgress.has(node)){ hasCycle =true;return;}// reached a node already on the current path — a cycleif(visited.has(node))return; inProgress.add(node);for(const neighbor of graph.get(node)??[]){dfs(neighbor);} inProgress.delete(node); visited.add(node); result.push(node);// postorder — Module P-4: push AFTER everything this node points to is fully explored}for(const node of graph.keys()){if(!visited.has(node))dfs(node);}return hasCycle ?null: result.reverse();}