Skip to content
RSS feed tkhwang on GitHub tkhwang on Twitter

Topological Sort in javascript

✨ Algorithm

  • Build adjacent lists graph and dependency indegrees.
  • Find zero dependency node which has indegrees[node] === 0 and push it to queue for BFS.
  • BFS traversal from zero dependency node.
  • Store current node cur to the final result orders[].
  • Whenever traversing the next node next, decrease the dependency by one indegrees[next] - 1.
    • If its dependency becomes zero, push it to the queue and visit next.

🔥 Topological Sort 

const topologicalSort = (N, prerequisites) => {
  const graph = {};
  const indegrees = Array(N).fill(0);

  for (const [course, precourse] of prerequisites) {
    if (graph[precourse] === undefined) graph[precourse] = [];
    graph[precourse].push(course);
    indegrees[course] += 1;
  }

  const queue = [];
  const orders = [];

  // find zero dependency
  for (let i = 0; i < N; i += 1) {
    if (indegrees[i] === 0) queue.push(i);
  }

  // bfs
  while (queue.length) {
    const len = queue.length;

    for (let i = 0; i < len; i += 1) {
      const cur = queue.shift();

      orders.push(cur);

      if (graph[cur] === undefined) continue;
      for (const next of graph[cur]) {
        indegrees[next] -= 1;
        if (indegrees[next] === 0) queue.push(next);
      }
    }
  }

  return orders;
};

🗒️ Typical problems

🏷️ Related tags