Topological Sort (Kahn's Algorithm & DAGs)

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Dependency Resolution & Ordering

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

2. Why DAGs Matter

Topological sort resolves dependencies in package managers (npm, pnpm), build systems (Webpack, Vite), and college course prerequisites.

Course Dependencies:  [ Math 101 ] ──► [ Calculus ] ──► [ Machine Learning ]
                      [ CS 101   ] ──► [ Data Structures ] ──┘

Valid Topological Order: [ Math 101, CS 101, Calculus, Data Structures, Machine Learning ]

3. Kahn's Algorithm (BFS + In-Degrees)

1. Calculate the in-degree (number of incoming edges) for every vertex.
2. Enqueue all vertices with inDegree === 0 (nodes with no prerequisites).
3. Dequeue a vertex, add it to the topological order, and decrement the in-degree of its neighbors.
4. If a neighbor's in-degree reaches 0, enqueue it!

function topologicalSort(numCourses, prerequisites) {
  const inDegree = new Array(numCourses).fill(0);
  const adjList = new Map();

  for (let i = 0; i < numCourses; i++) adjList.set(i, []);

  for (const [course, prereq] of prerequisites) {
    adjList.get(prereq).push(course);
    inDegree[course]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const order = [];
  while (queue.length > 0) {
    const curr = queue.shift();
    order.push(curr);

    for (const neighbor of adjList.get(curr)) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  // If order contains all courses, no cycle exists!
  return order.length === numCourses ? order : [];
}

console.log(topologicalSort(4, [[1, 0], [2, 0], [3, 1], [3, 2]]));
// Output: [0, 1, 2, 3] or [0, 2, 1, 3]

4. Cycle Detection

If the graph contains a directed cycle (e.g. $A o B o A$), order.length < numCourses because nodes in the cycle never reach inDegree === 0.

5. Common Mistakes

• Applying to Graphs with Cycles: Topological sorting is mathematically impossible on cyclic graphs. Always verify order.length === totalVertices to detect cycles.

6. Next Steps

Use Kahn's algorithm for compilation task scheduling. Next, let's explore Dijkstra's Shortest Path Algorithm!