Cycle Detection and Topological Order

Two genuinely common frontend problems — "does this module import graph have a circular dependency" and "in what order should these dependent tasks run" — are both answered by the same graph algorithm: a DFS that tracks a bit more state than the plain visited set from the last lesson.

Why "visited" alone isn't enough for cycle detection

The graph BFS/DFS from the previous lesson tracked one thing: has this node ever been visited. That's enough to avoid infinite loops, but it can't actually detect a cycle, because it can't distinguish two very different situations that look identical to a plain visited set:

• Revisiting a node that's still an ancestor on the current path — the traversal has genuinely looped back on itself. This is a real cycle.
• Revisiting a node that was already fully explored via a separate, unrelated branch earlier — completely normal in a graph (a node can legitimately be reachable from more than one place). This is not a cycle.

The fix: three colors, not two

The standard technique tracks each node in one of three states:

• White — not yet visited at all.
• Gray — currently being explored, and still an ancestor on the current recursive path (its DFS call hasn't returned yet).
• Black — fully explored; every one of its descendants has already been processed, and its own DFS call has returned.

A cycle exists exactly when DFS encounters a gray node — that specifically means "this node is still an active ancestor of where I currently am," which can only happen if the path has looped back onto itself.

function hasCycle(graph) {
  const WHITE = 0, GRAY = 1, BLACK = 2;
  const color = new Map([...graph.keys()].map((node) => [node, WHITE]));
 
  function visit(node) {
    color.set(node, GRAY);
 
    for (const neighbor of graph.get(node) ?? []) {
      if (color.get(neighbor) === GRAY) return true;       // cycle! neighbor is a current ancestor
      if (color.get(neighbor) === WHITE && visit(neighbor)) return true;
    }
 
    color.set(node, BLACK); // fully done — safe to revisit from elsewhere, not a cycle
    return false;
  }
 
  for (const node of graph.keys()) {
    if (color.get(node) === WHITE && visit(node)) return true;
  }
 
  return false;
}

const circularImports = new Map([
  ["moduleA", ["moduleB"]],
  ["moduleB", ["moduleC"]],
  ["moduleC", ["moduleA"]], // back to moduleA — a cycle
]);
 
hasCycle(circularImports); // true

The companion problem: topological order

Once you know a dependency graph has no cycles (a DAG — directed acyclic graph), you can compute a valid build order: an ordering of every node such that each one comes after everything it depends on.

function topologicalSort(graph) {
  const visited = new Set();
  const result = [];
 
  function visit(node) {
    if (visited.has(node)) return;
    visited.add(node);
 
    for (const dependency of graph.get(node) ?? []) {
      visit(dependency);
    }
 
    result.push(node); // add AFTER all dependencies are fully processed
  }
 
  for (const node of graph.keys()) {
    visit(node);
  }
 
  return result.reverse(); // dependencies end up first once reversed
}

The trick: a node is only appended to result after every one of its dependencies has been fully visited — which means, by construction, it ends up later in result than anything it depends on. Reversing at the end produces "dependencies first" order — exactly a valid build sequence.

const buildDeps = new Map([
  ["app", ["ui", "utils"]],
  ["ui", ["utils"]],
  ["utils", []],
]);
 
topologicalSort(buildDeps); // ["utils", "ui", "app"] — utils has no deps, so it builds first

If the graph does contain a cycle, no valid topological order can exist at all — some module would need to be built both before and after another, which is exactly the contradiction a real circular-import error is reporting. In practice, you'd run hasCycle first (or notice topologicalSort's result doesn't include every node, which is the tell-tale sign of an undetected cycle in a naive implementation) before trusting the build order.

Both are O(V + E)

Both algorithms are a single DFS pass: each node is processed a constant number of times, and each edge is followed exactly once. That gives O(V + E) — proportional to the graph's total size (V nodes plus E connections), the standard bound for any single graph traversal, and structurally the same "visit everything once" argument as tree traversal's O(n), generalized to a structure with both nodes and edges to account for.

What to remember

• Plain "visited" tracking can't detect cycles — it can't distinguish a real loop-back from a harmless re-visit via a separate branch. Three-color tracking (white/gray/black) makes that distinction: gray specifically means "still an ancestor on the current path."
• A cycle is detected exactly when DFS encounters a gray node.
• Topological sort produces a valid dependency order by appending a node to the result only after all its dependencies are fully processed, then reversing — and it only exists at all when the graph has no cycles.
• Both algorithms are O(V + E), the standard single-traversal bound for graphs — the same "visit everything once" idea as tree traversal, extended to account for edges as well as nodes.