jsschools

Topological Sort

Orders the vertices of a DAG (Directed Acyclic Graph) such that every directed edge u→v appears with u before v; implemented via DFS post-order or Kahn's BFS algorithm.

Spec ↗

Syntax

topoSort(graph)

Parameters

NameTypeRequiredDescription
graph Map<number, number[]> Yes Directed adjacency list representing a DAG. If the graph has a cycle, the algorithm returns null (Kahn's) or a partial order (DFS).

Returns

number[] | null — Topological order of vertices, or null if a cycle is detected (Kahn's).

Examples

// Kahn's algorithm (BFS-based)
function topoSort(graph) {
  const inDegree = new Map();
  for (const [u, neighbours] of graph) {
    if (!inDegree.has(u)) inDegree.set(u, 0);
    for (const v of neighbours) inDegree.set(v, (inDegree.get(v) ?? 0) + 1);
  }
  const queue = [...inDegree.entries()].filter(([, d]) => d === 0).map(([u]) => u);
  const order = [];
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (const v of graph.get(u) ?? []) {
      const d = inDegree.get(v) - 1;
      inDegree.set(v, d);
      if (d === 0) queue.push(v);
    }
  }
  return order.length === graph.size ? order : null; // null = cycle
}

const dag = new Map([
  [5, [2, 0]],
  [4, [0, 1]],
  [2, [3]],
  [3, [1]],
  [1, []],
  [0, []],
]);
console.log(topoSort(dag));
Output 
[ 5, 4, 2, 0, 3, 1 ]

// Cycle detection: returns null
function topoSort(graph) {
  const inDeg = new Map();
  for (const [u,ns] of graph) { if(!inDeg.has(u)) inDeg.set(u,0); for(const v of ns) inDeg.set(v,(inDeg.get(v)??0)+1); }
  const q = [...inDeg.entries()].filter(([,d])=>d===0).map(([u])=>u);
  const order = [];
  while(q.length) { const u=q.shift(); order.push(u); for(const v of graph.get(u)??[]) { const d=inDeg.get(v)-1; inDeg.set(v,d); if(d===0) q.push(v); } }
  return order.length===graph.size ? order : null;
}

const cyclic = new Map([[0,[1]],[1,[2]],[2,[0]]]);
console.log(topoSort(cyclic));
Output 
null

Notes

| Case | Time | Space | |---------|----------|-------| | Best | O(V + E) | O(V) | | Average | O(V + E) | O(V) | | Worst | O(V + E) | O(V) | Two standard approaches: (1) Kahn's BFS — processes nodes with in-degree 0 first; naturally detects cycles. (2) DFS post-order — push to a stack after visiting all descendants, then reverse. Both produce valid orderings but may differ in which valid order they choose. Topological sort is the foundation for build systems, task scheduling, course prerequisites, and evaluating cells in a spreadsheet DAG.

See also