BFS and DFS: Walking a Graph

You have a graph and you want to visit every node reachable from some starting point. There are two standard ways to do it, and here is the thing nobody tells you up front: they are the same algorithm. The only difference is whether you pull work off the front of the pile or the back.

The shared skeleton

Both traversals keep a pile of nodes they know about but have not looked at yet. Repeat until the pile is empty: take one out, mark it visited, and put its unvisited neighbours in. That is the whole algorithm.

Watch them race

Same graph, same start node. Hit Play on BFS, then switch the tab to DFS and play it again. Watch the queue and stack panel on the right as you go, because that container is doing all the work of deciding what happens next.

BFS visits A, then both of A's neighbours, then everything two steps out. It finishes each ring before starting the next. DFS commits to one direction and follows it until it hits a dead end, then reverses back to the last place it had an untaken option.

Click a different node to restart from there. Starting somewhere in the middle makes the ring-by-ring pattern of BFS much more obvious than starting at a corner.

Now switch to the "Two routes" example above, which makes the difference impossible to miss. There are two ways from A round to D: a long way over the top through B and C, and a short hop underneath through E. BFS visits E second, because it is one step from A and BFS checks everything one step away before going further. DFS visits E last, because it commits to the top route immediately and only comes back for E once it has run out of everything else. Same graph, same start, and a node that is one hop away gets found either immediately or dead last depending on which container you used.

BFS in code

function bfs(adj, start) {
  const visited = new Set([start]);
  const order = [];
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();   // <- take from the FRONT
    order.push(node);

    for (const next of adj.get(node) ?? []) {
      if (visited.has(next)) continue;
      visited.add(next);          // mark on the way IN, not on the way out
      queue.push(next);
    }
  }
  return order;
}

That comment about marking on the way in matters. If you only mark a node visited when you pull it off the queue, the same node can get queued several times before you ever reach it. The algorithm still terminates, but it does redundant work, and on a dense graph that gets expensive fast.

DFS in code, twice

Swap the queue for a stack and you have DFS. Literally change shift to pop:

function dfs(adj, start) {
  const visited = new Set();
  const order = [];
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop();     // <- take from the BACK
    if (visited.has(node)) continue;
    visited.add(node);
    order.push(node);

    for (const next of adj.get(node) ?? []) {
      if (!visited.has(next)) stack.push(next);
    }
  }
  return order;
}

DFS is also the one that writes naturally as a recursive function, because the call stack is already a stack. This version is shorter and it is the one you will see most often:

function dfsRecursive(adj, node, visited = new Set(), order = []) {
  if (visited.has(node)) return order;
  visited.add(node);
  order.push(node);

  for (const next of adj.get(node) ?? []) {
    dfsRecursive(adj, next, visited, order);
  }
  return order;
}

Be aware that the recursive version blows the call stack on very deep graphs. A path of a hundred thousand nodes will crash it in most languages. The iterative version has no such limit because its stack lives on the heap, which is why production code sometimes uses the uglier one on purpose.

The BFS trick worth remembering

On an unweighted graph, BFS finds the shortest path, and it does so for free. Because it expands ring by ring, the first time it reaches a node is necessarily by a path with the fewest possible hops. There is no way to reach it sooner, because everything closer was already checked.

To recover the actual path and not just the distance, remember which node you came from when you first queue each node, then walk those pointers backwards from the destination at the end.

// inside the neighbour loop:
parent.set(next, node);

// afterwards, rebuild the route:
function pathTo(parent, target) {
  const path = [target];
  while (parent.has(path[0])) path.unshift(parent.get(path[0]));
  return path;
}

DFS gives you no such guarantee. It will happily find a forty-step route to a node that sits two steps away, because it committed to a direction early and kept going. If you need shortest and your edges are all equal, use BFS.

Picking one

What to take away

BFS and DFS share one skeleton and differ by a single choice: take from the front of the queue and you explore in rings, take from the back and you explore in one long dive. That choice is the whole algorithm. If you remember nothing else, remember that BFS on an unweighted graph gives you shortest paths for free, because it reaches every node in the fewest possible hops.

Both run in O(V + E) when your graph is stored as an adjacency list. The moment edges carry different costs, fewest hops stops meaning cheapest and you need Dijkstra's algorithm instead. If any of the vocabulary here felt shaky, what a graph actually is covers the groundwork.

Check yourself

Sources and further reading

Wikipedia's breadth-first search and depth-first search articles both include the original references, including Edward F. Moore's 1959 paper, which is where BFS in its modern form comes from.

The Python examples use collections.deque, which pops from either end in O(1). Using a plain list and calling pop(0) is O(n) per step and quietly turns a linear traversal into a quadratic one.

BFS handles shortest paths when every edge costs the same. Put numbers on those edges and it stops working, which is where the next lesson picks up.