Topological patterns

The shape: dependencies want to be a line

A topological order of a directed graph is any ordering of its vertices such that for every edge u → v, u appears before v. It is the answer to every "in what order can I do these tasks given these prerequisites" question — build systems, course schedules, package managers, spreadsheet recalculation, and a surprising number of string and DP problems in disguise.

One theorem carries the whole chapter: a topological order exists if and only if the graph is a DAG (directed, acyclic). A cycle a → b → a demands that a come before b and after it, which no ordering can satisfy. That turns every topological sort into a free cycle detector — and interviewers exploit this constantly, which is why "Course Schedule I" (can it be done at all?) and "Course Schedule II" (give me the order) are the same code with a different return statement.

The order is generally not unique. If two tasks have no dependency path between them, either may go first. Any valid order is accepted; say this out loud, because a candidate who assumes a unique answer often writes a comparison-based sort by mistake.

Kahn's algorithm — BFS over in-degrees

Count how many prerequisites each node has. Everything with zero goes in the queue. Pop one, emit it, and decrement the counter of everything it points at; whenever a counter hits zero, that node's last blocker just cleared, so push it. If you emit fewer than n nodes, the leftovers are all stuck waiting on each other — a cycle.

// edges are [prereq, dependent] pairs. O(V + E) time, O(V + E) space.
function topoSortKahn(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [u, v] of edges) { adj[u].push(v); indeg[v]++; }

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

  const order = [];
  for (let head = 0; head < queue.length; head++) { // moving index, NOT queue.shift()
    const u = queue[head];
    order.push(u);
    for (const v of adj[u]) {
      if (--indeg[v] === 0) queue.push(v); // last prerequisite cleared — v is now free
    }
  }

  return order.length === n ? order : []; // short order ⇒ a cycle blocked the rest
}

Walking the diagram's graph, with edges 0→1, 0→2, 1→3, 2→3, 3→4:

Step 2 is the one to notice: node 3's counter drops from 2 to 1 and nothing happens. Pushing on "decremented" instead of "reached zero" is the single most common bug in this algorithm, and it produces an order that looks plausible on small examples but violates a prerequisite on any node with two parents.

Two free bonuses fall out of this structure and both come up as follow-ups: the number of nodes popped in a single "round" (drain the entire queue before starting the next) is the count of tasks that can run in parallel, and the number of rounds is the minimum time to finish everything with unlimited workers — which is also the longest path length. Also, if at any point the queue holds more than one node, the topological order is not unique; that is exactly the test for "is there a unique ordering" (Sequence Reconstruction).

DFS topological sort — post-order, then reverse

The DFS version comes at it from the opposite end. Recurse into all of a node's descendants first, and only after they have all been emitted, append the node itself. That builds the order backwards: a node always lands after everything it depends on, so reversing the finished list gives a valid topological order.

Cycle detection is where this version earns its keep — and where it is most often written wrong. A single visited boolean is not enough. You need three states, because seeing an already-visited node means two very different things depending on whether that node is still on the current recursion stack.

const WHITE = 0, GRAY = 1, BLACK = 2; // unvisited / on current path / fully explored

function topoSortDfs(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) adj[u].push(v);

  const state = new Array(n).fill(WHITE);
  const order = [];
  let cyclic = false;

  function dfs(u) {
    state[u] = GRAY; // entering: u is now on the recursion stack

    for (const v of adj[u]) {
      if (state[v] === GRAY) { cyclic = true; return; } // back edge into the current path
      if (state[v] === WHITE) {
        dfs(v);
        if (cyclic) return; // unwind immediately, don't finish this node
      }
      // state[v] === BLACK: cross/forward edge to finished work — safely ignored
    }

    state[u] = BLACK; // leaving: everything reachable from u is already in `order`
    order.push(u);    // POST-order push — this is what makes the reversal correct
  }

  for (let i = 0; i < n; i++) {
    if (state[i] === WHITE) {
      dfs(i);
      if (cyclic) return []; // no valid order exists
    }
  }

  return order.reverse();
}

Default to Kahn in an interview. It is iterative (no stack-depth caveat), the cycle check is a one-line length comparison, and the in-degree array is the hook for every follow-up question. Reach for DFS when you need the actual cycle, or when the same traversal is already computing something else post-order.

Course Schedule I and II — the canonical pair

"Can you finish all numCourses given prerequisites where [a, b] means you must take b before a?" is Course Schedule I. Course Schedule II asks for the ordering itself. One function answers both.

function findOrder(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);

  for (const [course, prereq] of prerequisites) {
    adj[prereq].push(course); // EDGE DIRECTION: prereq -> course, i.e. reversed from the input pair
    indeg[course]++;
  }

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

  const order = [];
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    order.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) queue.push(v);
  }

  return order.length === numCourses ? order : [];
}

// Course Schedule I is the same call, thrown away down to a boolean
const canFinish = (n, prereqs) => findOrder(n, prereqs).length === n;

Follow-ups that reuse this exact code: return the lexicographically smallest valid order (replace the queue with a min-heap, cost becomes O(V log V + E)); find the minimum number of semesters if unlimited courses can be taken in parallel (count BFS rounds); detect whether the ordering is unique (a round where the queue held ≥ 2 nodes means it is not).

Alien Dictionary — deriving the graph is the hard part

Given a list of words sorted by an unknown alphabet's order, recover that order. The topological sort at the end is boilerplate; the interview is testing whether you can extract the edges correctly. Two rules do it: compare each adjacent pair of words, and from that pair take only the first position where they differ — everything after it is unconstrained, because lexicographic comparison stopped there.

function alienOrder(words) {
  const adj = new Map(), indeg = new Map();
  for (const w of words) {
    for (const ch of w) {
      if (!adj.has(ch)) { adj.set(ch, new Set()); indeg.set(ch, 0); } // every seen letter must appear in the answer
    }
  }

  for (let i = 0; i + 1 < words.length; i++) {
    const a = words[i], b = words[i + 1];

    // "abc" before "ab" is impossible in ANY alphabet — invalid input, not a cycle
    if (a.length > b.length && a.startsWith(b)) return "";

    for (let j = 0; j < Math.min(a.length, b.length); j++) {
      if (a[j] !== b[j]) {
        if (!adj.get(a[j]).has(b[j])) { // dedupe: a repeated edge would double-count in-degree
          adj.get(a[j]).add(b[j]);
          indeg.set(b[j], indeg.get(b[j]) + 1);
        }
        break; // ONLY the first difference carries information — stop comparing
      }
    }
  }

  const queue = [...indeg.keys()].filter((c) => indeg.get(c) === 0);
  let out = "";
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    out += u;
    for (const v of adj.get(u)) {
      indeg.set(v, indeg.get(v) - 1);
      if (indeg.get(v) === 0) queue.push(v);
    }
  }

  return out.length === indeg.size ? out : ""; // cycle ⇒ the input was contradictory
}

Three failure modes, three different causes, and an interviewer will probe all of them. Prefix violation (["abc", "ab"]) — caught before the loop; it is not a graph problem at all. Cycle (["a","b","a"]) — caught by the length check at the end. Insufficient information (["z","x"] says nothing about y) — not an error; any order among the unconstrained letters is accepted, which is exactly why every letter seen anywhere must be seeded into the maps up front, even letters with no edges at all.

Longest path in a DAG — DP over the topological order

Longest path is NP-hard on a general graph, but on a DAG it is linear. The reason is exactly the property topological order gives you: when you process node u, every edge into u has already been processed, so dist[u] is final and can be relaxed outward without ever being revisited. That is the same argument Dijkstra makes with a priority queue — here the ordering is free and, crucially, negative weights are fine.

// edges: [u, v, weight]. Returns the longest path length in the whole DAG. O(V + E).
function longestPath(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [u, v, w] of edges) { adj[u].push([v, w]); indeg[v]++; }

  const order = [];
  const queue = [];
  const remaining = indeg.slice(); // copy — we still need the original to seed sources
  for (let i = 0; i < n; i++) if (remaining[i] === 0) queue.push(i);
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    order.push(u);
    for (const [v] of adj[u]) if (--remaining[v] === 0) queue.push(v);
  }
  if (order.length !== n) throw new Error("cycle: longest path is unbounded");

  const dist = new Array(n).fill(-Infinity);
  for (let i = 0; i < n; i++) if (indeg[i] === 0) dist[i] = 0; // any source can start a path

  for (const u of order) {
    if (dist[u] === -Infinity) continue;
    for (const [v, w] of adj[u]) {
      dist[v] = Math.max(dist[v], dist[u] + w); // dist[u] is FINAL — topo order guarantees it
    }
  }

  return Math.max(...dist);
}

Flip Math.max to Math.min and you have shortest path on a DAG, which beats Dijkstra's O(E log V) and — unlike Dijkstra — handles negative edge weights correctly. This is worth knowing as a named fact: "if the graph is a DAG, shortest path is O(V + E) by topological order, and negative weights are not a problem."

Once you see this, a whole family of problems reveals itself as topological DP where the graph is implicit and never built:

Recognizing it in an unseen problem

• The words "prerequisite," "depends on," "must come before," "build order," "compile," "recipe/ingredient," or any input of ordered pairs [a, b] meaning "a then b."
• The question is "is this even possible?" — that is cycle detection, and a topological sort answers it as a side effect (emitted count < n).
• Sorted or ranked input that implies relative order between symbols (Alien Dictionary, Sequence Reconstruction, Verifying an Alien Dictionary's harder cousins) — the edges must be derived, and only adjacent pairs at the first differing position carry information.
• "Minimum number of rounds/semesters/steps with unlimited parallelism" → Kahn, counting BFS levels. "Is the order unique?" → check whether the queue ever holds two nodes at once.
• Longest/shortest/count-of paths where the graph provably has no cycles → do not reach for Dijkstra or Bellman-Ford; relax edges in topological order for O(V + E), negative weights included.
• Distinguish from plain BFS/DFS: ordinary traversal visits a node the first time it is reached; topological sort must wait until every incoming edge is satisfied. If a node has two parents and you emit it after seeing only one, you have written BFS, not a topological sort.
• Distinguish from Union-Find: undirected connectivity and cycle detection in an undirected graph is Union-Find's job; direction and ordering is this chapter's.