Topological Sort: Code Templates in 6 Languages
If the ordering logic is still fuzzy, the concept guide walks through Kahn’s algorithm and the DFS alternative with visuals. This page is the memorizable part. It gives you the exact code for each approach in six languages, ready to adapt in an interview.
Main Template: Kahn’s Algorithm
This is the version to reach for first. It returns a valid order, and if the graph contains a cycle it returns an empty list, which is the signal that no order exists. The graph is given as a node count plus a list of directed edges, where the edge [u, v] means u must come before v.
Use this directly for Course Schedule and Course Schedule II .
function topologicalSort(n, edges) {
const adj = Array.from({ length: n }, () => []);
const indegree = new Array(n).fill(0);
const order = [];
for (const [u, v] of edges) {
adj[u].push(v);
// Each incoming edge is one prerequisite v still has
indegree[v]++;
}
// Nodes with no prerequisites can be placed immediately
const queue = [];
for (let i = 0; i < n; i++) {
if (indegree[i] === 0) queue.push(i);
}
while (queue.length > 0) {
const u = queue.shift();
order.push(u);
for (const v of adj[u]) {
// Removing u satisfies one prerequisite of v
indegree[v]--;
if (indegree[v] === 0) queue.push(v);
}
}
// Nodes stuck in a cycle never reach indegree 0,
// so a short order means the graph is cyclic
return order.length === n ? order : [];
}Code Breakdown
Key Variables
adj: the adjacency list.adj[u]holds every node v that depends on u.indegree: an array whereindegree[i]is the number of prerequisites node i still has. It starts as the count of incoming edges and only moves downward.queue: holds every node whose prerequisites are all satisfied, meaning nodes that are ready to be placed.order: the final topological order being built.
Visual Mechanism
graph TD
A["Count indegrees, build adjacency list"] --> B["Queue every node with indegree 0"]
B --> C{"Queue empty?"}
C -->|No| D["Pop u and append to order"]
D --> E["For each neighbor v: lower indegree"]
E --> F{"Neighbor indegree 0?"}
F -->|Yes| G["Queue that neighbor"]
G --> C
F -->|No| C
C -->|Yes| H{"Order length equals n?"}
H -->|Yes| I["Return order"]
H -->|No| J["Return empty: cycle"]
Critical Sections
The graph building step sets the edge convention. The edge [u, v] means u before v, so the indegree of v increases and v lands in the adjacency list of u. Get this direction wrong and the algorithm silently produces a reversed or partial order, so it is worth a mental check before moving on.
The seeding step scans every node once and queues all of them that start with indegree zero. A DAG can have several sources, and skipping this step for any of them loses an entire component of the answer.
The peeling loop is where the work happens. Popping u means u is placed, and each neighbor of u loses exactly one prerequisite. The moment a neighbor hits zero it joins the queue, because nothing else can be waiting on it anymore.
The verification step is the cycle detector. If a cycle exists, its nodes never reach indegree zero and never enter the queue, so the order comes up short. Comparing the length against n turns that silent failure into an explicit one.
Variations
1. DFS-Based Ordering
Recursion replaces the queue. Each node is marked in progress when entered, done when it finishes, and appended to the order when done. The order is reversed at the end. This is the right answer when the interviewer asks for a DFS approach or when the graph is small enough that recursion depth is safe.
Complexity:
function topologicalSortDFS(n, edges) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) adj[u].push(v);
const state = new Array(n).fill(0);
const order = [];
function dfs(u) {
state[u] = 1;
for (const v of adj[u]) {
// A node still in progress is a back edge
if (state[v] === 1) return false;
if (state[v] === 0 && !dfs(v)) return false;
}
state[u] = 2;
// Append on finish so dependents come first,
// then reverse the whole list at the end
order.push(u);
return true;
}
for (let i = 0; i < n; i++) {
if (state[i] === 0 && !dfs(i)) return [];
}
return order.reverse();
}2. Lexicographically Smallest Order
When the problem asks for the smallest valid order, swap the queue for a min-heap. The heap always hands back the lowest-numbered ready node, so the order comes out lexicographically smallest. This costs a log factor on every push and pop.
Complexity:
class MinHeap {
constructor() {
this.arr = [];
}
push(x) {
this.arr.push(x);
let i = this.arr.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.arr[p] <= this.arr[i]) break;
[this.arr[p], this.arr[i]] = [this.arr[i], this.arr[p]];
i = p;
}
}
pop() {
const top = this.arr[0];
const last = this.arr.pop();
if (this.arr.length > 0) {
this.arr[0] = last;
let i = 0;
while (true) {
let l = 2 * i + 1, r = 2 * i + 2, m = i;
if (l < this.arr.length && this.arr[l] < this.arr[m]) m = l;
if (r < this.arr.length && this.arr[r] < this.arr[m]) m = r;
if (m === i) break;
[this.arr[m], this.arr[i]] = [this.arr[i], this.arr[m]];
i = m;
}
}
return top;
}
get size() {
return this.arr.length;
}
}
function topologicalSortLexicographic(n, edges) {
const adj = Array.from({ length: n }, () => []);
const indegree = new Array(n).fill(0);
for (const [u, v] of edges) {
adj[u].push(v);
indegree[v]++;
}
const heap = new MinHeap();
for (let i = 0; i < n; i++) {
if (indegree[i] === 0) heap.push(i);
}
const order = [];
while (heap.size > 0) {
const u = heap.pop();
order.push(u);
for (const v of adj[u]) {
indegree[v]--;
if (indegree[v] === 0) heap.push(v);
}
}
return order.length === n ? order : [];
}Now head to the practice problems to apply these templates to real interview questions.