Topological Sort

Topological Sort

A topological sort produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every edge u → v, vertex u comes before v in the ordering.

Use Case: Course Scheduling

Imagine courses with prerequisites:

Math → Physics → Quantum
Math → Statistics
Statistics → ML

A topological sort gives a valid order to take all courses: e.g., Math, Physics, Statistics, Quantum, ML.

Kahn's Algorithm (BFS)

1. Compute the in-degree (number of incoming edges) for every node.
2. Add all nodes with in-degree 0 to a queue.
3. While the queue is not empty:
   • Dequeue a node, add it to the result.
   • For each neighbor, decrement its in-degree.
   • If a neighbor's in-degree reaches 0, enqueue it.
4. If the result contains all nodes, the sort is valid. Otherwise the graph has a cycle.

function topologicalSort(graph) {
  const inDegree = {};
  for (const node in graph) {
    if (!(node in inDegree)) inDegree[node] = 0;
    for (const neighbor of graph[node]) {
      inDegree[neighbor] = (inDegree[neighbor] || 0) + 1;
    }
  }

  const queue = [];
  for (const node in inDegree) {
    if (inDegree[node] === 0) queue.push(node);
  }

  const result = [];
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of (graph[node] || [])) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return result;
}

Complexity

Your Task

Implement topologicalSort(graph) using Kahn's algorithm. The graph is an adjacency list (object mapping node → array of neighbors). Return an array of nodes in topological order.