It orders vertices so every directed edge u→v goes from earlier to later. It exists only for a DAG (directed acyclic graph); any cycle means no valid topological order.
function topoSort(n: number, edges: Array<[number, number]>) {
const indeg = Array(n).fill(0);
const g: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
g[u].push(v);
indeg[v]++;
}
const q: number[] = [];
for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
const order: number[] = [];
while (q.length) {
const u = q.shift()!;
order.push(u);
for (const v of g[u]) {
indeg[v]--;
if (indeg[v] === 0) q.push(v);
}
}
return order.length === n ? order : null; // null => cycle
}Topological sort is an ordering of a directed graph consistent with dependencies: prerequisites come first. It exists iff the graph has no directed cycles.
Two standard ways to compute it: