How does topological sort work?

Topological order is only defined for a DAG. If the graph has a cycle, no valid order exists. Common uses are build systems, dependency resolution, course scheduling and task pipelines.

function topologicalSort(graph, nodes) {
  const indegree = new Map(nodes.map((node) => [node, 0]));
  for (const node of nodes) {
    for (const next of graph.get(node) || []) {
      indegree.set(next, (indegree.get(next) || 0) + 1);
    }
  }
  const queue = nodes.filter((node) => indegree.get(node) === 0);
  let head = 0;
  const order = [];
  while (head < queue.length) {
    const node = queue[head];
    head += 1;
    order.push(node);
    for (const next of graph.get(node) || []) {
      indegree.set(next, indegree.get(next) - 1);
      if (indegree.get(next) === 0) queue.push(next);
    }
  }
  return order.length === nodes.length ? order : [];
}

Kahn's algorithm versus DFS

• Kahn: compute indegrees, process zero-indegree nodes, decrement neighbours
• DFS: recurse into neighbours, then prepend the node to the order
• Kahn detects cycles naturally when fewer than V nodes are processed
• DFS detects cycles with a recursion-path set
• Both run in O(V + E) with an adjacency list

The order is not unique. Any valid sequence that respects every dependency is correct. If a problem requires a specific tie-break, use a heap or sort the zero-indegree set.