Complexity of Topological Sort

Introduction

Before a compiler can build your program it must sort the source files. Before a course scheduler can enroll you in Advanced Algorithms it must check you've passed Discrete Math. Before npm installs a package it must install that package's own dependencies first. All three problems share a single shape: put things in an order where every prerequisite comes before the thing that needs it.

The mathematical object behind this shape is a directed acyclic graph (DAG) — dots connected by arrows, with no way to follow arrows in a circle back to where you started. Each dot is a task; each arrow says "this must come before that." A topological ordering is any sequence of the dots where every arrow points only forward.

The remarkable fact is that such an ordering can always be found in linear time — $O(V + E)$ , where V is the number of tasks and E the number of dependencies. No backtracking, no guessing, no exponential blowup. The only obstacle is a cycle: if task A depends on B which depends on A, no valid order exists, and the algorithm detects this immediately.

Two classic algorithms find topological orders: Kahn's algorithm (1962), which repeatedly plucks tasks with no remaining prerequisites, and depth-first search (DFS) post-order reversal, which was noted by Knuth and later taught in every algorithms textbook. Both run in $O(V + E)$ time.

Try It

Build your own dependency graph below. Add tasks (nodes) and dependencies (directed edges), then click Sort to run Kahn's algorithm and watch a valid ordering appear. Introduce a cycle and the algorithm will catch it.

<div class="hint">Build a dependency graph: type a node name and click <b>Add Node</b>, then choose two nodes and click <b>Add Edge</b> (arrow from A → B means "A must come before B"). Click <b>Sort</b> to run Kahn’s algorithm.</div>
<div class="controls">
  <div class="row">
    <input id="nodeName" type="text" placeholder="Node name (e.g. A)" maxlength="12" />
    <button id="addNode" type="button">Add Node</button>
  </div>
  <div class="row">
    <select id="edgeFrom"></select>
    <span class="arrow-label">→</span>
    <select id="edgeTo"></select>
    <button id="addEdge" type="button">Add Edge</button>
  </div>
  <div class="row">
    <button id="sortBtn" type="button" class="primary">Sort</button>
    <button id="stepBtn" type="button">Step</button>
    <button id="resetBtn" type="button" class="ghost">Reset</button>
    <button id="exampleBtn" type="button" class="ghost">Load example</button>
  </div>
</div>
<canvas id="canvas" width="560" height="220"></canvas>
<div class="result" id="result">Add nodes and edges, then click Sort or Step.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.4; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .5rem; }
.row { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; }
input, select { font: 14px system-ui, sans-serif; padding: .3rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; background: #fff; }
input { width: 130px; }
select { max-width: 110px; }
.arrow-label { font-weight: 700; color: #1d3557; }
button { font: 600 13px system-ui, sans-serif; padding: .3rem .75rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.primary { background: #2a7ac5; border-color: #2a7ac5; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; width: 100%; border: 1px solid #cdd9e3; border-radius: 8px; background: #f8fafc; }
.result { font-size: .9rem; font-weight: 600; margin-top: .5rem; min-height: 1.5em; padding: .4rem .6rem; border-radius: 6px; background: #e8eef3; color: #1d3557; white-space: pre-wrap; }
.result.ok { background: #d4edda; color: #155724; }
.result.err { background: #f8d7da; color: #721c24; }
.result.step { background: #fff3cd; color: #856404; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Kahn’s algorithm: topological sort using in-degree counts and a queue.
// Nodes with in-degree 0 are processed first; each processed node reduces
// the in-degree of its successors. If all nodes are processed, we have a valid topological order. If not, a cycle was detected.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

// Graph state
let nodes = [];      // [{id, label, x, y}]
let edges = [];      // [{from, to}]  (id references)
let nodeIdCounter = 0;

// Animation state for Kahn’s
let kahnState = null; // null = not running, else {inDeg, queue, order, processed, currentId, done, cycle}

// ── Layout helpers ───────────────────────────────────────────────
function layoutNodes() {
  const W = canvas.width, H = canvas.height;
  const n = nodes.length;
  if (n === 0) return;
  // Arrange in a circle with some padding
  const cx = W / 2, cy = H / 2, r = Math.min(W, H) * 0.36;
  nodes.forEach((node, i) => {
    const angle = (2 * Math.PI * i / n) - Math.PI / 2;
    node.x = cx + r * Math.cos(angle);
    node.y = cy + r * Math.sin(angle);
  });
}

// ── Drawing ──────────────────────────────────────────────────────
const NODE_R = 22;
const COLORS = {
  default: { fill: '#e8eef3', stroke: '#1d3557', text: '#1d3557' },
  queued:  { fill: '#fff3cd', stroke: '#856404', text: '#856404' },
  active:  { fill: '#2a7ac5', stroke: '#1a5a95', text: '#fff' },
  done:    { fill: '#d4edda', stroke: '#155724', text: '#155724' },
  cycle:   { fill: '#f8d7da', stroke: '#721c24', text: '#721c24' },
};

function nodeState(node) {
  if (!kahnState) return 'default';
  const id = node.id;
  if (kahnState.cycleSet && kahnState.cycleSet.has(id)) return 'cycle';
  if (kahnState.processed.has(id)) return 'done';
  if (id === kahnState.currentId) return 'active';
  if (kahnState.queueSet && kahnState.queueSet.has(id)) return 'queued';
  return 'default';
}

function drawArrow(x1, y1, x2, y2, color) {
  const dx = x2 - x1, dy = y2 - y1;
  const len = Math.hypot(dx, dy);
  if (len < 1) return;
  const ux = dx / len, uy = dy / len;
  // Shorten to node edge
  const sx = x1 + ux * NODE_R, sy = y1 + uy * NODE_R;
  const ex = x2 - ux * NODE_R, ey = y2 - uy * NODE_R;
  ctx.beginPath();
  ctx.moveTo(sx, sy);
  ctx.lineTo(ex, ey);
  ctx.strokeStyle = color;
  ctx.lineWidth = 1.8;
  ctx.stroke();
  // Arrowhead
  const aw = 9, ah = 6;
  const px = -uy, py = ux;
  ctx.beginPath();
  ctx.moveTo(ex, ey);
  ctx.lineTo(ex - ux * aw + px * ah, ey - uy * aw + py * ah);
  ctx.lineTo(ex - ux * aw - px * ah, ey - uy * aw - py * ah);
  ctx.closePath();
  ctx.fillStyle = color;
  ctx.fill();
}

function draw() {
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  // Edges
  edges.forEach(e => {
    const fn = nodes.find(n => n.id === e.from);
    const tn = nodes.find(n => n.id === e.to);
    if (!fn || !tn) return;
    const edgeColor = '#6c757d';
    drawArrow(fn.x, fn.y, tn.x, tn.y, edgeColor);
  });

  // Nodes
  nodes.forEach(node => {
    const s = COLORS[nodeState(node)];
    ctx.beginPath();
    ctx.arc(node.x, node.y, NODE_R, 0, 2 * Math.PI);
    ctx.fillStyle = s.fill;
    ctx.fill();
    ctx.strokeStyle = s.stroke;
    ctx.lineWidth = 2;
    ctx.stroke();
    ctx.fillStyle = s.text;
    ctx.font = 'bold 13px system-ui, sans-serif';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(node.label, node.x, node.y);

    // In-degree badge
    if (kahnState && !kahnState.done) {
      const deg = kahnState.inDeg[node.id] ?? 0;
      ctx.fillStyle = '#6c757d';
      ctx.font = '10px system-ui, sans-serif';
      ctx.fillText('↓' + deg, node.x, node.y + NODE_R + 10);
    }
  });
}

// ── Select helpers ───────────────────────────────────────────────
function refreshSelects() {
  const from = document.getElementById('edgeFrom');
  const to = document.getElementById('edgeTo');
  [from, to].forEach(sel => {
    const prev = sel.value;
    sel.innerHTML = '';
    nodes.forEach(n => {
      const opt = document.createElement('option');
      opt.value = n.id;
      opt.textContent = n.label;
      sel.appendChild(opt);
    });
    if (nodes.some(n => String(n.id) === prev)) sel.value = prev;
  });
}

// ── Graph mutations ──────────────────────────────────────────────
function addNode(label) {
  if (!label) return;
  if (nodes.some(n => n.label === label)) return;
  nodes.push({ id: nodeIdCounter++, label, x: 0, y: 0 });
  layoutNodes();
  refreshSelects();
  kahnState = null;
  draw();
}

function addEdge(fromId, toId) {
  fromId = Number(fromId); toId = Number(toId);
  if (fromId === toId) return;
  if (edges.some(e => e.from === fromId && e.to === toId)) return;
  edges.push({ from: fromId, to: toId });
  kahnState = null;
  draw();
}

// ── Kahn’s algorithm, step-by-step ───────────────────────────────────────────
function initKahn() {
  const inDeg = {};
  const adj = {};
  nodes.forEach(n => { inDeg[n.id] = 0; adj[n.id] = []; });
  edges.forEach(e => { inDeg[e.to]++; adj[e.from].push(e.to); });
  const queue = nodes.filter(n => inDeg[n.id] === 0).map(n => n.id);
  const queueSet = new Set(queue);
  kahnState = {
    inDeg, adj,
    queue: [...queue],
    queueSet,
    order: [],
    processed: new Set(),
    currentId: null,
    done: false,
    cycleSet: null,
  };
}

function stepKahn() {
  if (!kahnState) initKahn();
  if (kahnState.done) return;

  if (kahnState.queue.length === 0) {
    // Cycle detected
    const cycleNodes = nodes.filter(n => !kahnState.processed.has(n.id));
    kahnState.cycleSet = new Set(cycleNodes.map(n => n.id));
    kahnState.done = true;
    const cycleLabels = cycleNodes.map(n => n.label).join(', ');
    setResult(fmt(`Cycle detected! These nodes are stuck: %cycleLabels%
No valid topological order exists.`, { cycleLabels: cycleLabels }), 'err');
    draw();
    return;
  }

  const id = kahnState.queue.shift();
  kahnState.queueSet.delete(id);
  kahnState.processed.add(id);
  kahnState.order.push(id);
  kahnState.currentId = id;

  // Reduce in-degrees of successors
  kahnState.adj[id].forEach(succ => {
    kahnState.inDeg[succ]--;
    if (kahnState.inDeg[succ] === 0) {
      kahnState.queue.push(succ);
      kahnState.queueSet.add(succ);
    }
  });

  const orderLabels = kahnState.order.map(i => nodes.find(n => n.id === i).label).join(' → ');

  if (kahnState.processed.size === nodes.length) {
    kahnState.done = true;
    kahnState.currentId = null;
    setResult(fmt(`✓ Topological order: %orderLabels%`, { orderLabels: orderLabels }), 'ok');
    console.log(`Topological order:`, orderLabels);
  } else {
    const remaining = nodes.length - kahnState.processed.size;
    setResult(fmt(`Step: processed %label%
Order so far: %orderLabels%
Queue: [%map%]
%remaining% node(s) remaining.`, { label: nodes.find(n => n.id === id).label, orderLabels: orderLabels, map: kahnState.queue.map(i => nodes.find(n => n.id === i).label).join(', '), remaining: remaining }), 'step');
  }
  draw();
}

function runKahn() {
  initKahn();
  // Run all steps at once
  let guard = 0;
  while (!kahnState.done && guard++ < 1000) stepKahn();
}

function setResult(text, cls) {
  const el = document.getElementById('result');
  el.textContent = text;
  el.className = 'result ' + (cls || '');
}

// ── Wiring ───────────────────────────────────────────────────────
document.getElementById('addNode').addEventListener('click', () => {
  const inp = document.getElementById('nodeName');
  addNode(inp.value.trim());
  inp.value = '';
});
document.getElementById('nodeName').addEventListener('keydown', e => {
  if (e.key === 'Enter') document.getElementById('addNode').click();
});
document.getElementById('addEdge').addEventListener('click', () => {
  const from = document.getElementById('edgeFrom').value;
  const to = document.getElementById('edgeTo').value;
  addEdge(from, to);
});
document.getElementById('sortBtn').addEventListener('click', () => {
  if (nodes.length === 0) { setResult(`Add at least one node first.`, 'err'); return; }
  runKahn();
});
document.getElementById('stepBtn').addEventListener('click', () => {
  if (nodes.length === 0) { setResult(`Add at least one node first.`, 'err'); return; }
  stepKahn();
});
document.getElementById('resetBtn').addEventListener('click', () => {
  nodes = []; edges = []; nodeIdCounter = 0; kahnState = null;
  refreshSelects();
  setResult(`Add nodes and edges, then click Sort or Step.`, '');
  draw();
});
document.getElementById('exampleBtn').addEventListener('click', () => {
  // Course prerequisite example: Math→Algo→DP, Math→DS→Algo, Prog→DS
  nodes = []; edges = []; nodeIdCounter = 0; kahnState = null;
  ['Math','Prog','DS','Algo','DP'].forEach(l => addNode(l));
  [['Math','Algo'],['Math','DS'],['Prog','DS'],['DS','Algo'],['Algo','DP']].forEach(([a,b]) => {
    addEdge(nodes.find(n => n.label===a).id, nodes.find(n => n.label===b).id);
  });
  setResult(`Example loaded: course prerequisites. Click Sort to order them.`, '');
});

// Initial draw
draw();

<div class="hint">Build a dependency graph: type a node name and click <b>Add Node</b>, then choose two nodes and click <b>Add Edge</b> (arrow from A → B means "A must come before B"). Click <b>Sort</b> to run Kahn’s algorithm.</div>
<div class="controls">
  <div class="row">
    <input id="nodeName" type="text" placeholder="Node name (e.g. A)" maxlength="12" />
    <button id="addNode" type="button">Add Node</button>
  </div>
  <div class="row">
    <select id="edgeFrom"></select>
    <span class="arrow-label">→</span>
    <select id="edgeTo"></select>
    <button id="addEdge" type="button">Add Edge</button>
  </div>
  <div class="row">
    <button id="sortBtn" type="button" class="primary">Sort</button>
    <button id="stepBtn" type="button">Step</button>
    <button id="resetBtn" type="button" class="ghost">Reset</button>
    <button id="exampleBtn" type="button" class="ghost">Load example</button>
  </div>
</div>
<canvas id="canvas" width="560" height="220"></canvas>
<div class="result" id="result">Add nodes and edges, then click Sort or Step.</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.4; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .5rem; }
.row { display: flex; align-items: center; gap: .4rem; flex-wrap: wrap; }
input, select { font: 14px system-ui, sans-serif; padding: .3rem .5rem; border: 1px solid #adb1b8; border-radius: 6px; background: #fff; }
input { width: 130px; }
select { max-width: 110px; }
.arrow-label { font-weight: 700; color: #1d3557; }
button { font: 600 13px system-ui, sans-serif; padding: .3rem .75rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; }
button.primary { background: #2a7ac5; border-color: #2a7ac5; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; width: 100%; border: 1px solid #cdd9e3; border-radius: 8px; background: #f8fafc; }
.result { font-size: .9rem; font-weight: 600; margin-top: .5rem; min-height: 1.5em; padding: .4rem .6rem; border-radius: 6px; background: #e8eef3; color: #1d3557; white-space: pre-wrap; }
.result.ok { background: #d4edda; color: #155724; }
.result.err { background: #f8d7da; color: #721c24; }
.result.step { background: #fff3cd; color: #856404; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Kahn’s algorithm: topological sort using in-degree counts and a queue.
// Nodes with in-degree 0 are processed first; each processed node reduces
// the in-degree of its successors. If all nodes are processed, we have a valid topological order. If not, a cycle was detected.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');

// Graph state
let nodes = [];      // [{id, label, x, y}]
let edges = [];      // [{from, to}]  (id references)
let nodeIdCounter = 0;

// Animation state for Kahn’s
let kahnState = null; // null = not running, else {inDeg, queue, order, processed, currentId, done, cycle}

// ── Layout helpers ───────────────────────────────────────────────
function layoutNodes() {
  const W = canvas.width, H = canvas.height;
  const n = nodes.length;
  if (n === 0) return;
  // Arrange in a circle with some padding
  const cx = W / 2, cy = H / 2, r = Math.min(W, H) * 0.36;
  nodes.forEach((node, i) => {
    const angle = (2 * Math.PI * i / n) - Math.PI / 2;
    node.x = cx + r * Math.cos(angle);
    node.y = cy + r * Math.sin(angle);
  });
}

// ── Drawing ──────────────────────────────────────────────────────
const NODE_R = 22;
const COLORS = {
  default: { fill: '#e8eef3', stroke: '#1d3557', text: '#1d3557' },
  queued:  { fill: '#fff3cd', stroke: '#856404', text: '#856404' },
  active:  { fill: '#2a7ac5', stroke: '#1a5a95', text: '#fff' },
  done:    { fill: '#d4edda', stroke: '#155724', text: '#155724' },
  cycle:   { fill: '#f8d7da', stroke: '#721c24', text: '#721c24' },
};

function nodeState(node) {
  if (!kahnState) return 'default';
  const id = node.id;
  if (kahnState.cycleSet && kahnState.cycleSet.has(id)) return 'cycle';
  if (kahnState.processed.has(id)) return 'done';
  if (id === kahnState.currentId) return 'active';
  if (kahnState.queueSet && kahnState.queueSet.has(id)) return 'queued';
  return 'default';
}

function drawArrow(x1, y1, x2, y2, color) {
  const dx = x2 - x1, dy = y2 - y1;
  const len = Math.hypot(dx, dy);
  if (len < 1) return;
  const ux = dx / len, uy = dy / len;
  // Shorten to node edge
  const sx = x1 + ux * NODE_R, sy = y1 + uy * NODE_R;
  const ex = x2 - ux * NODE_R, ey = y2 - uy * NODE_R;
  ctx.beginPath();
  ctx.moveTo(sx, sy);
  ctx.lineTo(ex, ey);
  ctx.strokeStyle = color;
  ctx.lineWidth = 1.8;
  ctx.stroke();
  // Arrowhead
  const aw = 9, ah = 6;
  const px = -uy, py = ux;
  ctx.beginPath();
  ctx.moveTo(ex, ey);
  ctx.lineTo(ex - ux * aw + px * ah, ey - uy * aw + py * ah);
  ctx.lineTo(ex - ux * aw - px * ah, ey - uy * aw - py * ah);
  ctx.closePath();
  ctx.fillStyle = color;
  ctx.fill();
}

function draw() {
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  // Edges
  edges.forEach(e => {
    const fn = nodes.find(n => n.id === e.from);
    const tn = nodes.find(n => n.id === e.to);
    if (!fn || !tn) return;
    const edgeColor = '#6c757d';
    drawArrow(fn.x, fn.y, tn.x, tn.y, edgeColor);
  });

  // Nodes
  nodes.forEach(node => {
    const s = COLORS[nodeState(node)];
    ctx.beginPath();
    ctx.arc(node.x, node.y, NODE_R, 0, 2 * Math.PI);
    ctx.fillStyle = s.fill;
    ctx.fill();
    ctx.strokeStyle = s.stroke;
    ctx.lineWidth = 2;
    ctx.stroke();
    ctx.fillStyle = s.text;
    ctx.font = 'bold 13px system-ui, sans-serif';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(node.label, node.x, node.y);

    // In-degree badge
    if (kahnState && !kahnState.done) {
      const deg = kahnState.inDeg[node.id] ?? 0;
      ctx.fillStyle = '#6c757d';
      ctx.font = '10px system-ui, sans-serif';
      ctx.fillText('↓' + deg, node.x, node.y + NODE_R + 10);
    }
  });
}

// ── Select helpers ───────────────────────────────────────────────
function refreshSelects() {
  const from = document.getElementById('edgeFrom');
  const to = document.getElementById('edgeTo');
  [from, to].forEach(sel => {
    const prev = sel.value;
    sel.innerHTML = '';
    nodes.forEach(n => {
      const opt = document.createElement('option');
      opt.value = n.id;
      opt.textContent = n.label;
      sel.appendChild(opt);
    });
    if (nodes.some(n => String(n.id) === prev)) sel.value = prev;
  });
}

// ── Graph mutations ──────────────────────────────────────────────
function addNode(label) {
  if (!label) return;
  if (nodes.some(n => n.label === label)) return;
  nodes.push({ id: nodeIdCounter++, label, x: 0, y: 0 });
  layoutNodes();
  refreshSelects();
  kahnState = null;
  draw();
}

function addEdge(fromId, toId) {
  fromId = Number(fromId); toId = Number(toId);
  if (fromId === toId) return;
  if (edges.some(e => e.from === fromId && e.to === toId)) return;
  edges.push({ from: fromId, to: toId });
  kahnState = null;
  draw();
}

// ── Kahn’s algorithm, step-by-step ───────────────────────────────────────────
function initKahn() {
  const inDeg = {};
  const adj = {};
  nodes.forEach(n => { inDeg[n.id] = 0; adj[n.id] = []; });
  edges.forEach(e => { inDeg[e.to]++; adj[e.from].push(e.to); });
  const queue = nodes.filter(n => inDeg[n.id] === 0).map(n => n.id);
  const queueSet = new Set(queue);
  kahnState = {
    inDeg, adj,
    queue: [...queue],
    queueSet,
    order: [],
    processed: new Set(),
    currentId: null,
    done: false,
    cycleSet: null,
  };
}

function stepKahn() {
  if (!kahnState) initKahn();
  if (kahnState.done) return;

  if (kahnState.queue.length === 0) {
    // Cycle detected
    const cycleNodes = nodes.filter(n => !kahnState.processed.has(n.id));
    kahnState.cycleSet = new Set(cycleNodes.map(n => n.id));
    kahnState.done = true;
    const cycleLabels = cycleNodes.map(n => n.label).join(', ');
    setResult(fmt(`Cycle detected! These nodes are stuck: %cycleLabels%
No valid topological order exists.`, { cycleLabels: cycleLabels }), 'err');
    draw();
    return;
  }

  const id = kahnState.queue.shift();
  kahnState.queueSet.delete(id);
  kahnState.processed.add(id);
  kahnState.order.push(id);
  kahnState.currentId = id;

  // Reduce in-degrees of successors
  kahnState.adj[id].forEach(succ => {
    kahnState.inDeg[succ]--;
    if (kahnState.inDeg[succ] === 0) {
      kahnState.queue.push(succ);
      kahnState.queueSet.add(succ);
    }
  });

  const orderLabels = kahnState.order.map(i => nodes.find(n => n.id === i).label).join(' → ');

  if (kahnState.processed.size === nodes.length) {
    kahnState.done = true;
    kahnState.currentId = null;
    setResult(fmt(`✓ Topological order: %orderLabels%`, { orderLabels: orderLabels }), 'ok');
    console.log(`Topological order:`, orderLabels);
  } else {
    const remaining = nodes.length - kahnState.processed.size;
    setResult(fmt(`Step: processed %label%
Order so far: %orderLabels%
Queue: [%map%]
%remaining% node(s) remaining.`, { label: nodes.find(n => n.id === id).label, orderLabels: orderLabels, map: kahnState.queue.map(i => nodes.find(n => n.id === i).label).join(', '), remaining: remaining }), 'step');
  }
  draw();
}

function runKahn() {
  initKahn();
  // Run all steps at once
  let guard = 0;
  while (!kahnState.done && guard++ < 1000) stepKahn();
}

function setResult(text, cls) {
  const el = document.getElementById('result');
  el.textContent = text;
  el.className = 'result ' + (cls || '');
}

// ── Wiring ───────────────────────────────────────────────────────
document.getElementById('addNode').addEventListener('click', () => {
  const inp = document.getElementById('nodeName');
  addNode(inp.value.trim());
  inp.value = '';
});
document.getElementById('nodeName').addEventListener('keydown', e => {
  if (e.key === 'Enter') document.getElementById('addNode').click();
});
document.getElementById('addEdge').addEventListener('click', () => {
  const from = document.getElementById('edgeFrom').value;
  const to = document.getElementById('edgeTo').value;
  addEdge(from, to);
});
document.getElementById('sortBtn').addEventListener('click', () => {
  if (nodes.length === 0) { setResult(`Add at least one node first.`, 'err'); return; }
  runKahn();
});
document.getElementById('stepBtn').addEventListener('click', () => {
  if (nodes.length === 0) { setResult(`Add at least one node first.`, 'err'); return; }
  stepKahn();
});
document.getElementById('resetBtn').addEventListener('click', () => {
  nodes = []; edges = []; nodeIdCounter = 0; kahnState = null;
  refreshSelects();
  setResult(`Add nodes and edges, then click Sort or Step.`, '');
  draw();
});
document.getElementById('exampleBtn').addEventListener('click', () => {
  // Course prerequisite example: Math→Algo→DP, Math→DS→Algo, Prog→DS
  nodes = []; edges = []; nodeIdCounter = 0; kahnState = null;
  ['Math','Prog','DS','Algo','DP'].forEach(l => addNode(l));
  [['Math','Algo'],['Math','DS'],['Prog','DS'],['DS','Algo'],['Algo','DP']].forEach(([a,b]) => {
    addEdge(nodes.find(n => n.label===a).id, nodes.find(n => n.label===b).id);
  });
  setResult(`Example loaded: course prerequisites. Click Sort to order them.`, '');
});

// Initial draw
draw();

Result

Console

Notice that each step of Kahn's algorithm picks any node whose in-degree (number of unsatisfied prerequisites) has reached zero. Multiple valid orderings often exist — any is acceptable as long as every arrow points forward. The moment a cycle is present, some nodes never reach in-degree zero, and the algorithm reports the cycle rather than an ordering.

The Real Complexity

Topological sort is a solved problem in the best possible sense: an optimal algorithm has been known since 1962, and the problem sits firmly in P — polynomial time — in fact in linear time.

Time: $O(V + E)$ . Every node is enqueued exactly once; every edge is examined exactly once. There is no smarter algorithm in the worst case because you must at minimum read every edge to know the dependency structure.
Space: $O(V + E)$ . You need to store the graph and an in-degree counter per node.
Cycle detection is free. At the end of Kahn's algorithm, if any node was never dequeued its in-degree never reached zero, which means it is part of a cycle. No extra pass is needed.
Not unique. There are often many valid orderings; if you want the lexicographically smallest, replace the queue with a min-heap (O((V + E) log V)).
Contrast with related hard problems. Finding a Hamiltonian path — visiting every node exactly once — is NP-complete. The difference is that a Hamiltonian path has no given direction constraints; any permutation might work or fail. Topological sort has the direction constraints built in, and that structure makes it easy.

Because topological sort is in P, it is never the bottleneck. Any algorithm that runs a topological sort as a subroutine inherits only the $O(V + E)$ overhead, and this subroutine is used liberally across the whole of computer science.

Where It Matters

Topological sort is one of those algorithms that quietly runs inside almost every piece of software infrastructure:

Build systems (Make, Ninja, Bazel, Gradle): a source file must be compiled before any file that includes it. The build graph is a DAG; topological sort gives the correct compilation order and — crucially — exposes which files can be compiled in parallel (those at the same depth).
Package managers (npm, pip, apt, Cargo): installing package A first requires installing A's dependencies. Circular dependencies are a package-manager error; the resolver reports them via cycle detection.
Course planning: universities generate valid course sequences by topologically sorting a prerequisite graph. The same idea applies to project management task sequencing.
Spreadsheet recalculation: when you change a cell, the spreadsheet engine topologically sorts the dependency graph of formulas and recomputes them in order — updating only what changed, in the right order, with no wasted work.
Data pipeline scheduling (Airflow, Luigi, dbt): each pipeline stage depends on upstream stages completing first. Topological sort defines the execution schedule, and the DAG view you see in pipeline UIs is literally the same structure.
Compiler internals: instruction scheduling, register allocation, and dead-code elimination all exploit topological orderings of control-flow and data-flow graphs.

The common thread is "there is a known partial order; I need a total order consistent with it." Topological sort solves exactly that, in the least time possible. See also shortest paths, where DAG shortest paths are solved optimally by processing nodes in topological order.

Conclusion

Topological sort is one of the most satisfying algorithms in all of computer science: the problem has an obvious structure, the algorithm is elegant, and the complexity is optimal. Feed it a DAG and it returns a valid ordering in linear time. Feed it a cycle and it tells you immediately — no valid ordering exists.

The broader lesson is that structure makes problems easy. The directed-acyclic structure of a dependency graph is exactly the gift that turns an otherwise combinatorial search into a single linear pass. Every time you encounter a problem that feels like "there must be a right order," ask whether the constraints form a DAG — if they do, topological sort hands you the answer in $O(V + E)$ . If they don't, you may be looking at something far harder, like P vs NP.

Comments

Loading comments...

https://www.kipuhub.com/en/article/topological-sort/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Topological Sort

When dependencies must come first