Graph search: BFS and DFS

In 1736 Leonhard Euler showed that no walk crosses each of Königsberg's seven bridges exactly once, and graph theory began with that answer.

Dots and lines

A graph is a set of points, called vertices or nodes, joined by lines, called edges. The idea is plain, and it fits a huge range of things: cities joined by roads, web pages joined by links, people joined by friendships, squares of a maze joined where there is no wall. Once a problem is drawn as a graph, the same handful of algorithms can answer questions like "can I get from here to there?" and "what is the shortest way?"

Storing a graph in code

A common way to store a graph is an adjacency list: for each vertex, a list of its neighbours. MIT's 6.006 notes use exactly this, an array or dictionary Adj where Adj[u] lists the vertices joined to u. For the graph above it looks like this:

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D", "E"],
  D: ["B", "C", "F"],
  E: ["C", "F"],
  F: ["D", "E"],
};

Breadth-first search: ring by ring

Breadth-first search (BFS) explores a graph in rings around the start. First the start itself, at distance 0. Then all its neighbours, at distance 1. Then every new vertex next to those, at distance 2, and so on. To do this it keeps a queue, a line where the first one in is the first one out. Take the vertex at the front of the queue, visit it, and add its unseen neighbours to the back. From A in the example, BFS visits A, then B and C, then D and E, then F. Because it moves outward one ring at a time, the first time BFS reaches a vertex it has found a path with the fewest edges. F is 3 edges from A, for example A, B, D, F.

function bfs(graph, start) {
  const seen = new Set([start]);
  const queue = [start];
  const order = [];
  while (queue.length) {
    const u = queue.shift();        // first in, first out
    order.push(u);
    for (const v of graph[u]) {
      if (!seen.has(v)) { seen.add(v); queue.push(v); }
    }
  }
  return order;   // A B C D E F
}

Depth-first search: as far as you can, then back up

Depth-first search (DFS) behaves like a person in a maze keeping one hand on the wall. It follows one path as deep as it can go. When it reaches a dead end or a place it has already seen, it backs up to the most recent choice point and tries the next option. It uses a stack instead of a queue, last in, first out, and is very natural to write with recursion, where the call stack does the remembering. From A, a recursive DFS visits A, B, D, C, E, F. DFS reaches every vertex BFS reaches, but the path it follows is not necessarily the shortest one.

function dfs(graph, u, seen = new Set(), order = []) {
  seen.add(u);
  order.push(u);
  for (const v of graph[u]) if (!seen.has(v)) dfs(graph, v, seen, order);
  return order;   // A B D C E F
}

Which one to use

In the lab's first maze, BFS visits 105 squares and finds a path of 22 moves, the shortest possible. DFS happens to dive toward the goal and visits only 31 squares, but its path takes 28 moves. Neither is always cheaper. Both handle each vertex and each edge a fixed number of times, so both run in O(V + E) time for V vertices and E edges. Choose BFS when you need the fewest steps: the fewest moves in a puzzle, the fewest links between two people. Choose DFS when you need to explore everything or follow choices to the end: checking whether every room of a maze connects, or trying the moves of a puzzle one line at a time and backing up when stuck. When edges have different lengths, as roads do, neither is enough on its own; methods such as Dijkstra's algorithm extend the BFS idea with distances.