Topological Sort

Topological Sort — DSA Tutorial - HTML5ANDCSS3

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

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

What it produces

Kahn's algorithm

Course schedule, the standard framing

Where you have already used it