Skip to main content
HTML5ANDCSS3 logoHTML5ANDCSS3Tools and Tutorials

Graphs

Topological Sort

Written by Updated

Any question about ordering things with dependencies is a topological sort. Course prerequisites, build steps, module imports, task schedules - same problem, different nouns.

What it produces

An ordering of a directed graph where every node appears before everything that depends on it. It only exists if there are no cycles - and detecting that impossibility is half the value.

Kahn's algorithm

Count how many things each node is waiting on. Start with those waiting on nothing. As each one completes, decrement its dependents; any that reach zero become available.

Kahn's algorithm

javascript

function topologicalSort(numNodes, edges) {
  const graph = Array.from({ length: numNodes }, () => [])
  const inDegree = new Array(numNodes).fill(0)

  // edge [a, b] means: a must come before b.
  for (const [a, b] of edges) {
    graph[a].push(b)
    inDegree[b]++
  }

  // Everything with nothing to wait for.
  const queue = []
  for (let i = 0; i < numNodes; i++) {
    if (inDegree[i] === 0) queue.push(i)
  }

  const order = []
  let head = 0

  while (head < queue.length) {
    const node = queue[head++]
    order.push(node)

    for (const next of graph[node]) {
      inDegree[next]--
      if (inDegree[next] === 0) queue.push(next)
    }
  }

  // Anything left has a cycle, so no valid order exists.
  return order.length === numNodes ? order : []
}

console.log(topologicalSort(4, [[0,1], [0,2], [1,3], [2,3]]))
// [0, 1, 2, 3]

console.log(topologicalSort(2, [[0,1], [1,0]]))
// [] — circular dependency

The final length check is the cycle detection. If some nodes never reached in-degree zero, they are waiting on each other forever.

Course schedule, the standard framing

Can these courses be completed?

javascript

// Repeated from above so this example runs on its own.
function topologicalSort(numNodes, edges) {
  const graph = Array.from({ length: numNodes }, () => [])
  const inDegree = new Array(numNodes).fill(0)

  for (const [a, b] of edges) { graph[a].push(b); inDegree[b]++ }

  const queue = []
  for (let i = 0; i < numNodes; i++) if (inDegree[i] === 0) queue.push(i)

  const order = []
  let head = 0
  while (head < queue.length) {
    const node = queue[head++]
    order.push(node)
    for (const next of graph[node]) {
      if (--inDegree[next] === 0) queue.push(next)
    }
  }

  return order.length === numNodes ? order : []
}

function canFinish(numCourses, prerequisites) {
  // [a, b] means: b must be taken before a.
  const edges = prerequisites.map(([a, b]) => [b, a])
  return topologicalSort(numCourses, edges).length === numCourses
}

console.log(canFinish(2, [[1, 0]]))          // true
console.log(canFinish(2, [[1, 0], [0, 1]]))  // false

Note the edge flip. "a requires b" means the edge runs b to a. Getting that backwards produces a confidently wrong answer, and it is the most common mistake here.

Where you have already used it

  • Bundlers - module import order.
  • Build systems - Make, task runners, CI pipelines.
  • Package managers - install order, and "circular dependency detected" is this check failing.
  • Spreadsheets - recalculating cells in dependency order.

O(nodes + edges) in time and space - the same as any graph traversal.

Detecting the impossible case

Kahn's algorithm gives you cycle detection for free. Count the nodes you managed to output - if it is fewer than the total, the leftovers are stuck waiting on each other, which means a cycle. There is no valid ordering, and saying so is often the point of the question.

Reporting the cycle

javascript

function ordering(numNodes, edges) {
  const graph = Array.from({ length: numNodes }, () => [])
  const inDegree = new Array(numNodes).fill(0)

  for (const [a, b] of edges) {
    graph[a].push(b)
    inDegree[b]++
  }

  const queue = []
  for (let i = 0; i < numNodes; i++) if (inDegree[i] === 0) queue.push(i)

  const order = []
  let head = 0
  while (head < queue.length) {
    const node = queue[head++]
    order.push(node)
    for (const next of graph[node]) {
      if (--inDegree[next] === 0) queue.push(next)
    }
  }

  return order.length === numNodes
    ? { ok: true, order }
    : { ok: false, reason: "cycle — no valid ordering exists" }
}

console.log(ordering(3, [[0, 1], [1, 2]]))
console.log(ordering(2, [[0, 1], [1, 0]]))

Note the index-based queue rather than shift() - the same O(1) dequeue point from the queues lesson, and it matters here because graphs get large.

The orderings are not unique

Whenever two nodes are both ready, either may come first, so a graph usually has many valid topological orderings. If a problem expects one specific answer it will add a tie-break rule - smallest index first, which means a priority queue instead of a plain one.

PreviousGraph Traversal: BFS and DFSNextDijkstra's Algorithm