DAY 24 / 30 · WEEK 4

Graphs II — Shortest Path & Topo Sort

Goal of the day

• Extend Day 23's BFS with exactly one new piece of bookkeeping — a distance map — to get the shortest path (fewest edges) in an unweighted graph, essentially for free.
• Learn topological sort via Kahn's algorithm: order the nodes of a directed graph with no cycles so that every edge points from an earlier node to a later one.
• Understand that topological sort only makes sense on a directed, acyclic graph (a DAG) — and that Kahn's algorithm detects a cycle as a natural side effect, instead of needing separate cycle-detection logic bolted on.

Concept

Shortest path in an unweighted graph. Day 23's bfs already does almost all of the work here — it just never told you how far away each node was. BFS explores level by level: it fully processes every node at distance 1 from the start before it ever looks at a node at distance 2. That ordering guarantee means the very first time BFS discovers a node, it has found that node by the shortest possible path (fewest edges). So the only new idea is to track a distance map alongside the visited set: distance[start] = 0, and every time a neighbor is discovered for the first time, it gets distance[current] + 1. Same queue, same visited-on-discovery rule, same traversal — one extra assignment per newly discovered node.

Topological sort. Picture a semester's prerequisite chart: Intro CS unlocks both Discrete Math and Data Structures; Discrete Math and Data Structures both feed into Algorithms; Data Structures also unlocks Databases; and Algorithms and Databases both feed into Systems Design. A topological sort answers "what order can I safely take these courses in?" — an ordering where every prerequisite appears before the course that depends on it. The exact same question shows up as "in what order do I compile these files given their #include dependencies?" or "in what order do I run these build steps?". Kahn's algorithm answers it with a BFS-shaped idea: compute every node's in-degree (how many prerequisites it still has), start a queue with every node whose in-degree is already 0 (no prerequisites), then repeatedly dequeue a node, append it to the result, and decrement the in-degree of everything it points to — enqueuing any neighbor that just dropped to 0.

Two things only make sense together here, and both are worth saying out loud in an interview: topological sort requires a directed graph (an undirected edge has no "prerequisite comes first" direction to exploit), and it only exists if that directed graph has no cycle. If Data Structures secretly required Systems Design and Systems Design required Data Structures, there would be no valid place to start — every course in that cycle is stuck waiting on another course in the same cycle. Kahn's algorithm doesn't need a separate check for this: if the graph has a cycle, some nodes never reach in-degree 0, so the final result comes up short of the total node count — a cycle announces itself by absence rather than by a crash or an infinite loop.

One deliberate scope note: today's shortest-path technique only works because every edge "costs" the same — one hop. If edges have different weights (e.g. road distances, flight prices), BFS's level-by-level order no longer lines up with the lowest-total-weight path, and you'd reach for Dijkstra's algorithm (BFS with a priority queue instead of a plain queue) instead. That's a topic for another day — the unweighted case below is what most interview "shortest path" questions on a plain graph actually want.

Diagram: BFS distances radiating from a start node

Diagram: a DAG with a valid topological order

Diagram: why a cycle makes topological sort impossible

Interactive visualization: BFS shortest path (distance tracking)

Interactive visualization: Kahn's algorithm (topological sort)

The code: BFS shortest path and Kahn's topological sort

// Shortest path (fewest edges) in an UNWEIGHTED graph — Day 23's bfs()
// with one new line: a distance map built up as each node is discovered.
function bfsShortestPath(graph, start) {
  const distance = { [start]: 0 };   // start is 0 hops from itself
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    for (const neighbor of graph[node]) {
      if (!(neighbor in distance)) {
        distance[neighbor] = distance[node] + 1;  // one hop further than `node`
        queue.push(neighbor);
      }
    }
  }
  return distance; // { nodeId: distanceFromStart }
}

// Topological sort of a DIRECTED ACYCLIC graph — Kahn's algorithm.
// graph[node] = array of nodes that DEPEND ON node (node must come first).
function topoSortKahn(graph, nodes) {
  const inDegree = {};
  nodes.forEach((n) => { inDegree[n] = 0; });
  for (const n of nodes) {
    for (const neighbor of graph[n]) {
      inDegree[neighbor] = (inDegree[neighbor] || 0) + 1;
    }
  }

  const queue = nodes.filter((n) => inDegree[n] === 0); // no prerequisites
  const order = [];

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

  const hasCycle = order.length !== nodes.length;
  return { order, hasCycle };
}

Line by line:

• bfsShortestPath: identical shape to Day 23's bfs — a queue, a "mark on discovery" rule — except the visited set is now a distance object. Membership in distance (via neighbor in distance) does the same job the visited Set did before; the value it stores is the new information.
• distance[neighbor] = distance[node] + 1 is the one genuinely new line. It's correct precisely because of BFS's level-by-level guarantee: by the time node is being processed, distance[node] is already final, so anything discovered from it is exactly one hop further out.
• Just like Day 23's trap, the neighbor must be marked (here: given a distance) at discovery time, not at dequeue time — otherwise the same node could be discovered through two different paths before either finishes processing, and whichever one happens to run last could overwrite a correct short distance with a longer, wrong one.
• topoSortKahn starts by computing every node's in-degree (count of incoming edges — prerequisites still owed) with one full pass over every node's neighbor list. This costs O(E) up front, separate from the traversal that follows.
• The queue seeds with every node that already has in-degree 0 — no prerequisites, safe to process immediately. This can be more than one node (as in the diagram above, where only A starts at 0, but a differently-shaped DAG could start with several).
• Each dequeue appends to order and decrements the in-degree of everything that node points to — "one of your prerequisites is now satisfied." A neighbor only joins the queue the instant its in-degree reaches exactly 0, i.e. every one of its prerequisites has been processed.
• hasCycle = order.length !== nodes.length is the whole cycle check. If every node eventually reaches in-degree 0, they all get processed and order has every node. If some nodes are stuck in a cycle, they never reach 0, the queue empties out early, and order comes up short — that gap is the cycle detection, no separate scan required.

Dry run: BFS shortest path from A (same graph as Day 23)

Final distances from A: A=0, B=1, C=1, D=2, E=3, G=3, F=4 — the same BFS order as Day 23 (A → B → C → D → E → G → F), just now with a number attached to each node the first time it's discovered.

Dry run: Kahn's algorithm on the course-prerequisite DAG

Final order: A → B → C → D → E → F — all 6 of 6 nodes processed, so hasCycle is false. This matches the diagram above exactly.

Complexity

Interview corner

• Why does plain BFS naturally give you the shortest path in an unweighted graph? BFS explores strictly level by level — everything at distance 1 is fully discovered before anything at distance 2 is even looked at. So the very first time a node is discovered, it's necessarily been reached by the fewest possible edges; there's no shorter path still waiting to be found later.
  ⚠ Trap: this guarantee is specific to unweighted graphs, where every edge counts as exactly 1 hop. The instant edges have different weights (distances, costs, times), BFS's level order no longer matches the lowest-total-weight path — that needs Dijkstra's algorithm (a priority queue instead of a plain queue), not plain BFS.
• Does the enqueue-vs-dequeue timing trap from Day 23 still apply here? Yes, in an even more consequential form. distance[neighbor] must be assigned the moment a node is discovered (enqueued), not when it's later dequeued — a node can be "discoverable" through more than one path before it's ever processed, and marking at dequeue time risks a later, longer path overwriting the correct, already-found shortest distance.
• Why does topological sort only make sense on a directed, acyclic graph? "Topological order" means "every prerequisite before its dependent," which requires a direction to even ask the question — an undirected edge has no defined "which one comes first." And if the graph has a cycle, some node ends up (directly or transitively) depending on itself — no linear order can satisfy that, so no valid ordering exists at all, not just an ambiguous one.
  ↳ Common follow-up: "How do you detect that cycle instead of just returning something wrong?" — that's Kahn's algorithm's built-in signal: if order.length ends up less than the total node count, the leftover nodes never reached in-degree 0, meaning they're stuck in (or depend on) a cycle.
• What breaks if you skip checking order.length === nodes.length and just trust whatever Kahn's algorithm produced?
  ⚠ Trap: on a cyclic graph you'd silently return a partial, incomplete order and the caller might treat it as valid. In "Course Schedule" terms: you'd incorrectly report that all courses can be completed when some are actually stuck in a prerequisite cycle. Always check the length — this is the single most-tested edge case for this algorithm.
• Is Kahn's algorithm the only way to topologically sort a graph? No — a DFS-based approach also works: run DFS from every unvisited node, and prepend each node to the result the moment its DFS call finishes (post-order), which naturally puts dependents after their dependencies. Kahn's is usually preferred in interviews because the in-degree bookkeeping doubles as cycle detection with no extra code, where the DFS version needs a separate "currently on this DFS path" set to catch a cycle.

How to talk through it out loud: for shortest path, say the connection first — "this is the same BFS as Day 23, I'm just adding a distance map that increments by one each time I discover a new node" — so the interviewer hears you reusing a known-correct traversal rather than inventing something new. For topological sort, name the two preconditions before writing a line of code — "this only works because the graph is directed and, I'm assuming, acyclic — I'll use Kahn's algorithm with in-degree counting, and if the result comes up short of the total node count, that tells me there's a cycle and no valid order exists." Interviewers on both of these are listening for whether you state the underlying guarantee (BFS's level-order; the DAG requirement) rather than just producing code that happens to work on the one example in front of you.

Practice problems

Note: this set is intentionally Easy/Medium/ Medium rather than Easy/Medium/Hard — there's no clean, distinct Easy-tier problem that exercises real topological-sort mechanics beyond in-degree counting, so problem 1 uses the in-degree idea alone (no queue/ordering) as the easy on-ramp, and problems 2-3 cover the two core techniques from today at Medium difficulty each.

function findJudge(n, trust) {
  const inDegree = new Array(n + 1).fill(0);  // trusted-by count
  const outDegree = new Array(n + 1).fill(0); // trusts count
  for (const [a, b] of trust) {
    outDegree[a]++;
    inDegree[b]++;
  }
  for (let person = 1; person <= n; person++) {
    if (outDegree[person] === 0 && inDegree[person] === n - 1) return person;
  }
  return -1;
}

function canFinish(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);
  for (const [course, pre] of prerequisites) {
    adj[pre].push(course);
    inDegree[course]++;
  }

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

  let visited = 0;
  while (queue.length > 0) {
    const node = queue.shift();
    visited++;
    for (const neighbor of adj[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }
  return visited === numCourses; // false means a cycle blocked some courses
}

function updateMatrix(mat) {
  const rows = mat.length, cols = mat[0].length;
  const dist = Array.from({ length: rows }, () => new Array(cols).fill(-1));
  const queue = [];

  // seed the queue with EVERY 0-cell at distance 0, not just one start node
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (mat[r][c] === 0) { dist[r][c] = 0; queue.push([r, c]); }
    }
  }

  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let qi = 0;
  while (qi < queue.length) {
    const [r, c] = queue[qi++];
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] === -1) {
        dist[nr][nc] = dist[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }
  return dist;
}

Quiz