Order nodes in a DAG so all dependencies come before dependents.
Topological sort produces a linear ordering of nodes in a Directed Acyclic Graph (DAG) such that for every directed edge u→v, node u appears before v. It is used for task scheduling, build systems, and course prerequisites.
O(V + E)
O(V)
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when the problem involves ordering tasks, courses, or nodes where some must come before others
A topological order only exists if the graph has no cycles. If a cycle is detected during sorting, the input is invalid and the problem is unsolvable.
Problem Course Schedule. Build a directed graph of prerequisites and attempt a topological sort; if any cycle is detected, return false.
function canFinish(n, prereqs) { const graph = Array.from({length: n}, () => []); const indeg = new Array(n).fill(0); for (const [a, b] of prereqs) { graph[b].push(a); indeg[a]++; } const q = []; for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i); let done = 0; while (q.length) { const u = q.shift(); done++; for (const v of graph[u]) if (--indeg[v] === 0) q.push(v); } return done === n; }Use this when you need a BFS-based topological sort that also naturally detects cycles
Build an indegree array, enqueue all nodes with indegree 0, then process them by decrementing neighbors' indegrees and enqueuing any that reach 0. If the total processed count equals the number of nodes, no cycle exists.
Problem Course Schedule II. Return the processing order from Kahn's; if count < n a cycle exists and return [].
function findOrder(n, prereqs) { const graph = Array.from({length: n}, () => []); const indeg = new Array(n).fill(0); for (const [a, b] of prereqs) { graph[b].push(a); indeg[a]++; } const q = [], order = []; for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i); while (q.length) { const u = q.shift(); order.push(u); for (const v of graph[u]) if (--indeg[v] === 0) q.push(v); } return order.length === n ? order : []; }Use this when you prefer a recursive DFS-based topological sort
After fully exploring all descendants of a node, push it to a stack. Reverse the stack at the end for the final order. Track three states per node: unvisited, in-progress, and done — if you revisit an in-progress node, a cycle exists.
Problem Alien Dictionary. Build a character-order graph, run DFS topological sort, and reverse the result.
function topoSort(graph, n) { const state = new Array(n).fill(0); const stack = []; let hasCycle = false;Use this when the problem asks whether a directed graph contains a cycle, which is equivalent to asking whether a topological order exists
In Kahn's algorithm, a cycle is present if the number of processed nodes is less than the total. In DFS, a cycle is detected when a back-edge to an in-progress node is found.
Problem Detect Cycle in Directed Graph. Run Kahn's; if processed count < n, there is a cycle.
function hasCycle(n, edges) { const graph = Array.from({length: n}, () => []); const indeg = new Array(n).fill(0); for (const [u, v] of edges) { graph[u].push(v); indeg[v]++; } const q = []; for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i); let count = 0; while (q.length) { const u = q.shift(); count++; for (const v of graph[u]) if (--indeg[v] === 0) q.push(v); } return count < n; }Use this when implementing Kahn's algorithm to track which nodes are ready to process
The indegree of a node is the number of directed edges pointing into it. A node is ready (can be scheduled next) only when its indegree reaches 0, meaning all its dependencies have been resolved.
Problem Parallel Courses. The minimum number of semesters equals the longest path in the DAG, found by tracking the layer each node is processed in during Kahn's.
function minSemesters(n, relations) { const graph = Array.from({length: n+1}, () => []); const indeg = new Array(n+1).fill(0); for (const [u, v] of relations) { graph[u].push(v); indeg[v]++; } const q = []; for (let i = 1; i <= n; i++) if (indeg[i] === 0) q.push([i, 1]); let ans = 0, done = 0; while (q.length) { const [u, sem] = q.shift(); done++; ans = Math.max(ans, sem); for (const v of graph[u]) if (--indeg[v] === 0) q.push([v, sem+1]); } return done === n ? ans : -1; }Use topological sort whenever a problem involves dependencies, prerequisites, or ordering constraints on a DAG
Common applications: course scheduling, build order, task dependency resolution, and finding the shortest/longest path in a DAG.
Problem Find All Recipes. Model ingredients and recipes as a graph, add a virtual source node pointing to all available ingredients, then run topological sort and collect all reachable recipe nodes.
function findAllRecipes(recipes, ingredients, supplies) { const graph = {}, indeg = {}; const recipeSet = new Set(recipes); for (const r of recipes) { graph[r] = []; indeg[r] = 0; } for (let i = 0; i < recipes.length; i++) for (const ing of ingredients[i]) { if (!graph[ing]) graph[ing] = []; graph[ing].push(recipes[i]); if (recipeSet.has(recipes[i])) indeg[recipes[i]]++; } const q = [...supplies.filter(s => graph[s])]; const res = []; while (q.length) { const u = q.shift(); if (recipeSet.has(u)) res.push(u); for (const v of (graph[u]||[])) if (--indeg[v] === 0) q.push(v); } return res; }