Day 24: Graphs II — Shortest Path & Topo Sort

DAY 24 / 30 · WEEK 4

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

        A(0)
       / \
     B(1) C(1)
       |   |
      D(2)
      / \
    E(3) G(3)
    |
   F(4)

Same graph as Day 23 — BFS from A, now labeling each node’s distance. B and C are A’s direct neighbors, so both get distance 1. D is 2 hops away, reachable only through B or C. E and G are 3 hops out through D, and F is the farthest at 4 hops.

Diagram: a DAG with a valid topological order

    Intro CS (A)
       / \
      /   \
   Disc   Data
   Math   Struct
    (B)   (C)
       \ /  \
        |    \
       Algo   \
        (D)    \
        / \     \
       /   \    Db
      /     \   (E)
    Sys     \ /
    Design  /
     (F)---

Course prerequisites as a DAG — every edge points from prereq to dependent. Valid order: A → B → C → D → E → F — every arrow points from an earlier course to a later one. A → C → B → D → E → F is valid too — a DAG can have more than one correct topological order.

Diagram: why a cycle makes topological sort impossible

    X → Y
    ↑   ↓
    └─ Z

A directed 3-cycle: X needs Y, Y needs Z, Z needs X. Every node is stuck waiting on a node that’s waiting on it — no node ever has in-degree 0. Kahn’s algorithm’s queue starts (and stays) empty — order.length is 0, never 3. That gap (0 processed nodes out of 3 total) is exactly how Kahn’s algorithm reports “no valid order.”

Interactive visualization: BFS shortest path & Kahn’s topological sort

Interactive visualization: BFS shortest path (distance tracking)

in the queue (distance recorded, waiting) dequeued, checking neighbors now fully processed — distance finalized

Press Play or Step to begin.

Step 0 / ...

Interactive visualization: Kahn's algorithm (topological sort)

in-degree just hit 0 — enqueued, waiting dequeued now — decrementing its neighbors' in-degree added to the topological order

Press Play or Step to begin.

Step 0 / ...

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)

Queue (before)	Dequeue	Neighbor checks	Distance map (after)
[A]	A (dist 0)	B new → dist 1, enqueue; C new → dist 1, enqueue	`{A:0, B:1, C:1}`
[B, C]	B (dist 1)	A has a distance, skip; D new → dist 2, enqueue	`{A:0, B:1, C:1, D:2}`
[C, D]	C (dist 1)	A has a distance, skip; D has a distance, skip	`{A:0, B:1, C:1, D:2}`
[D]	D (dist 2)	B, C have distances, skip; E new → dist 3, enqueue; G new → dist 3, enqueue	`{A:0, B:1, C:1, D:2, E:3, G:3}`
[E, G]	E (dist 3)	D has a distance, skip; F new → dist 4, enqueue	`{..., F:4}`
[G, F]	G (dist 3)	D has a distance, skip	`{..., F:4}`
[F]	F (dist 4)	E has a distance, skip	`{A:0, B:1, C:1, D:2, E:3, F:4, G:3}`

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

Queue (before)	Dequeue → order	Decrement neighbors’ in-degree	Newly 0 → enqueue	Queue (after)
[A]	A	B: 1→0, C: 1→0	B, C	[B, C]
[B, C]	B	D: 2→1	(none, still waiting on C)	[C]
[C]	C	D: 1→0, E: 1→0	D, E	[D, E]
[D, E]	D	F: 2→1	(none, still waiting on E)	[E]
[E]	E	F: 1→0	F	[F]
[F]	F	(no neighbors — nothing depends on F)	(none)	[]

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

Operation	Time	Space	Why
BFS shortest path (distance tracking)	O(V + E)	O(V)	Exactly Day 23’s plain BFS — every vertex is enqueued and processed once, every edge is examined once per endpoint. Recording a distance is O(1) extra work per newly discovered node, so it doesn’t change the bound.
Topological sort (Kahn’s algorithm)	O(V + E)	O(V)	Computing every node’s in-degree scans all edges once (O(E)). Each node enters and leaves the queue exactly once (O(V)), and each edge is examined exactly once when decrementing a neighbor’s in-degree (O(E)) — no node or edge is revisited.
Cycle detection (side effect of Kahn’s)	O(1) extra	O(1) extra	Just compare order.length to the total node count after the algorithm finishes — no separate traversal is needed to detect the cycle.

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.

1. Find the Town Judge

Easy — LeetCode: Find the Town Judge

In a town of n people, the judge trusts nobody but is trusted by everyone else. Given a list of [a, b] “a trusts b” pairs, find the judge, or return -1 if none exists.

Hint

This is the same in-degree/out-degree bookkeeping Kahn’s algorithm uses, without the queue. Track two counts per person: out-degree (how many people they trust) and in-degree (how many people trust them). The judge is the one person with out-degree 0 and in-degree exactly n - 1.

Solution

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;
}

2. Course Schedule

Medium — LeetCode: Course Schedule

Given numCourses and a list of [course, prerequisite] pairs, return whether it’s possible to finish all courses. The direct, unmodified application of today’s Kahn’s algorithm.

Hint

Build the directed graph as prerequisite → course, run Kahn’s algorithm exactly as in today’s code, and compare how many courses got processed against numCourses — if fewer, some courses are stuck in a prerequisite cycle and can never be taken.

Solution

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
}

3. 01 Matrix

Medium — LeetCode: 01 Matrix

Given a binary matrix, return a matrix where each cell holds the distance to its nearest 0-cell. Today’s distance-tracking BFS, generalized to start from every 0-cell at once instead of a single start node — multi-source BFS.

Hint

Seed the queue with every 0-cell at distance 0 simultaneously (not just one), same as any BFS but with multiple starting points instead of one. Everything else — level-by-level expansion, marking distance the instant a cell is first discovered — is identical to today’s bfsShortestPath.

Solution

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

1. Why does plain BFS find the shortest path (fewest edges) in an unweighted graph?

Because BFS explores level by level, so the first discovery of any node is always via the fewest edges
Because BFS always processes nodes in alphabetical/sorted order
It doesn’t — BFS and DFS find equally short paths on any graph

Answer: Because BFS explores level by level, so the first discovery of any node is always via the fewest edges

2. When would BFS’s shortest-path approach give the WRONG answer, and what would you use instead?

When edges have different weights — use Dijkstra’s algorithm (a priority queue) instead
Never — BFS always finds the true shortest path on any graph, weighted or not
When the graph is directed — use DFS instead

Answer: When edges have different weights — use Dijkstra’s algorithm (a priority queue) instead

3. In Kahn’s algorithm, what does it mean when order.length ends up less than the total number of nodes?

The graph has a cycle — the leftover nodes never reached in-degree 0
The graph is simply disconnected, which is fine and expected
It always means there’s a bug in the in-degree calculation

Answer: The graph has a cycle — the leftover nodes never reached in-degree 0

4. In Kahn’s algorithm, which nodes go into the queue first?

Every node whose in-degree is already 0 — no unmet prerequisites
The node with the highest number of outgoing edges
Any single arbitrary starting node, same as BFS/DFS traversal

Answer: Every node whose in-degree is already 0 — no unmet prerequisites

5. What is the time complexity of Kahn’s algorithm, and why?

O(V + E) — every node and edge is processed exactly once, same as BFS/DFS
O(V²) — every node must be compared against every other node
O(E log V) — it needs a priority queue like Dijkstra’s algorithm

Answer: O(V + E) — every node and edge is processed exactly once, same as BFS/DFS