Breadth first, depth first

The same code, twice

A stack gives depth first; a queue gives breadth first. That is the entire difference, and it is worth internalising: the algorithm is identical and only the container changes.

Mark a node as seen when you add it to the frontier, not when you take it out. Doing it on the way out lets the same node be queued several times before it is first processed, which is a subtle bug that only shows up on graphs with many paths to the same place.

function traverse(graph, start, takeNext) {
  const seen = new Set([start]);
  const frontier = [start];
  const order = [];

  while (frontier.length) {
    const node = takeNext(frontier);            // pop → depth first
    order.push(node);                           // shift/head → breadth first

    for (const next of graph.get(node) ?? []) {
      if (seen.has(next)) continue;             // ← without this it never ends
      seen.add(next);
      frontier.push(next);
    }
  }

  return order;
}

BFS finds the shortest path — when the edges are equal

Because BFS expands everything one step away, then everything two steps away, the first time it reaches a node is by a shortest route. That guarantee holds only while every edge costs the same — the moment they differ you need Dijkstra, which is the next lesson.

The cameFrom map is the general technique for recovering a path: store where each node was reached from, then walk backwards from the goal.

function shortestPath(graph, start, goal) {
  const cameFrom = new Map([[start, null]]);
  const queue = [start];

  for (let head = 0; head < queue.length; head++) {
    const node = queue[head];
    if (node === goal) break;

    for (const next of graph.get(node) ?? []) {
      if (cameFrom.has(next)) continue;
      cameFrom.set(next, node);                 // remember how we arrived
      queue.push(next);
    }
  }

  if (!cameFrom.has(goal)) return null;

  const path = [];
  for (let at = goal; at !== null; at = cameFrom.get(at)) path.push(at);

  return path.reverse();
}

DFS goes deep, and answers different questions

A cycle is an edge back to a node that is still open — still on the current path. An edge to a done node is fine: that is just two routes to the same place. Getting this distinction right is the difference between detecting a cycle and calling every diamond a cycle.

This is what npm reports as a circular dependency, what a spreadsheet calls a circular reference, and what a deadlock detector looks for.

/* recursive DFS, with the three colours that detect a cycle */
function hasCycle(graph) {
  const state = new Map();                      // undefined | "open" | "done"

  const visit = (node) => {
    if (state.get(node) === "open") return true;    // back to a node still on the stack
    if (state.get(node) === "done") return false;   // already fully explored

    state.set(node, "open");
    for (const next of graph.get(node) ?? []) if (visit(next)) return true;
    state.set(node, "done");

    return false;
  };

  return [...graph.keys()].some(visit);
}

Topological order

Start with everything that depends on nothing, and each time you finish a node, decrement its dependants. Anything that reaches zero is now ready. That is exactly how make, a package installer, a task runner and a migration tool decide what to do next — and the leftover nodes, if any, are the cycle.

Kahn's algorithm — BFS over in-degrees

function topoOrder(graph) {
  const inDegree = new Map([...graph.keys()].map((n) => [n, 0]));
  for (const edges of graph.values()) for (const to of edges) inDegree.set(to, inDegree.get(to) + 1);

  const ready = [...inDegree].filter(([, d]) => d === 0).map(([n]) => n);
  const order = [];

  for (let head = 0; head < ready.length; head++) {
    const node = ready[head];
    order.push(node);
    for (const next of graph.get(node) ?? []) {
      inDegree.set(next, inDegree.get(next) - 1);
      if (inDegree.get(next) === 0) ready.push(next);
    }
  }

  return order.length === graph.size ? order : null;    // null means there is a cycle
}

Which to use

Both are O(n + e): every node once, every edge once. The difference is which answer you get first, and how much memory the frontier holds — BFS can hold a whole level, which on a wide graph is most of the nodes.

Question	Use
Shortest path, equal edges	BFS
Is there any path?	Either
Connected components, flood fill	Either — DFS is shorter
Cycle detection, topological order	DFS, or Kahn
Nearest match, fewest moves, word ladder	BFS
Exploring all possibilities, backtracking	DFS
A very deep graph	BFS, or iterative DFS — recursion will overflow

The same code, twice

BFS finds the shortest path — when the edges are equal

DFS goes deep, and answers different questions

Topological order

Which to use

Practice