Topological Sort

Topological Sort

Imagine you have a list of tasks where some tasks must be done before others. Like getting dressed — you can't put on socks before underwear! Topological sort finds a valid order that respects all these dependencies.

This only works on DAGs (Directed Acyclic Graphs). If there's a cycle, there's no valid ordering because task A depends on B, B depends on C, and C depends on A — a catch-22!

Kahn's Algorithm (BFS-based)

Kahn's algorithm is elegant. First, calculate the in-degree (number of incoming edges) for each vertex. Then, start with all vertices that have in-degree 0 — these are tasks with no dependencies.

Process these vertices, and for each one, reduce the in-degree of its neighbors by 1. If any neighbor's in-degree becomes 0, add it to the queue. Repeat until done. The result is a valid topological order!

function topologicalSort(graph) {
  const inDegree = {};
  const queue = [];
  const result = [];
  
  for (const vertex in graph) {
    inDegree[vertex] = 0;
  }
  for (const vertex in graph) {
    for (const neighbor of graph[vertex]) {
      inDegree[neighbor]++;
    }
  }
  
  for (const vertex in inDegree) {
    if (inDegree[vertex] === 0) {
      queue.push(vertex);
    }
  }
  
  while (queue.length > 0) {
    const current = queue.shift();
    result.push(current);
    
    for (const neighbor of graph[current]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }
  return result;
}

Real-World Applications

Topological sort is everywhere! Build systems like Make or npm use it to determine the order to compile modules. If module A imports module B, then B must be compiled first.

Course prerequisites are another classic example. You can't take "Advanced Algorithms" before "Data Structures." Task scheduling, spreadsheet calculations, and even clothing order — all use topological sort under the hood.

const prerequisites = {
  "CS101": ["CS102"],
  "CS102": ["CS201"],
  "Math101": ["CS201"],
  "CS201": []
};

DFS-based Topological Sort

There's also a DFS-based approach. Run DFS and add vertices to a stack in post-order (after processing all neighbors). Then reverse the stack to get the topological order. It's like saying goodbye to everyone before leaving the party!

Both approaches are O(V + E) time complexity, so performance isn't a factor. Choose whichever feels more natural — Kahn's is often easier to understand and debug.

function dfsTopologicalSort(graph) {
  const visited = new Set();
  const stack = [];
  
  function dfs(vertex) {
    visited.add(vertex);
    for (const neighbor of graph[vertex]) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
    stack.push(vertex);
  }
  
  for (const vertex in graph) {
    if (!visited.has(vertex)) {
      dfs(vertex);
    }
  }
  return stack.reverse();
}