Data structures & algorithms2 min

Topological Sort

A Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $U \to V$, vertex $U$ comes before vertex $V$ in the ordering.

Real-Life Analogy

Think of University Course Prerequisites. You want to graduate.

  • You must take Intro to Programming before Data Structures.
  • You must take Data Structures before Algorithms.
  • You can take Calculus whenever, but it must be before Machine Learning.

If you represent courses as nodes, and prerequisites as directed edges, a Topological Sort gives you the exact semester-by-semester schedule you need to graduate without breaking any prerequisite rules!

[!WARNING] Topological Sort is mathematically impossible if the graph contains a Cycle. (e.g., Course A requires Course B, but Course B requires Course A. You are stuck in an infinite loop and can never take either).

Algorithm 1: Kahn's Algorithm (BFS Approach)

Kahn's Algorithm uses the concept of In-Degree (how many edges point into a node).

  1. Calculate the in-degree for every node.
  2. Find all nodes with an in-degree of 0 (These courses have no prerequisites!). Push them into a Queue.
  3. While the Queue is not empty:
    • Dequeue a node. Add it to the final sorted array.
    • For every neighbor of that node, subtract 1 from their in-degree (we just "completed" a prerequisite).
    • If a neighbor's in-degree hits 0, push it into the Queue.
  4. If the final array size is less than the total number of vertices, a Cycle exists!
typescript
function kahnTopologicalSort(numCourses: number, prerequisites: number[][]): number[] {
  const adjList = new Map<number, number[]>();
  const inDegree = new Array(numCourses).fill(0);
  
  // Build Graph and In-Degree array
  for (const [course, preq] of prerequisites) {
    if (!adjList.has(preq)) adjList.set(preq, []);
    adjList.get(preq)!.push(course);
    inDegree[course]++;
  }
  
  const queue: number[] = [];
  const result: number[] = [];
  
  // Enqueue nodes with 0 dependencies
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
  
  while (queue.length > 0) {
    const current = queue.shift()!;
    result.push(current);
    
    // Process neighbors
    const neighbors = adjList.get(current) || [];
    for (const next of neighbors) {
      inDegree[next]--; // Prerequisite completed!
      if (inDegree[next] === 0) {
        queue.push(next); // Ready to be taken!
      }
    }
  }
  
  // Cycle Detection Check
  if (result.length !== numCourses) return []; // Cycle found, impossible to sort
  
  return result;
}

Algorithm 2: Depth-First Search (DFS)

Topological Sort can also be done elegantly using recursive DFS.

The trick is to use a visited set to avoid infinite loops, and a path set to detect cycles. As DFS explores a node, it dives as deep as possible. When a node has no unvisited children left, it is pushed to a stack. Finally, popping elements off the stack yields the valid topological order.

  • Time Complexity: $O(V + E)$ for both algorithms. We visit every vertex and every edge once.
  • Space Complexity: $O(V + E)$ for storing the graph and the Queue/Stack.