Skip to content
Ayotl
Español

← Data structures from scratch · Lesson 25/32

Walking a graph: BFS and DFS

✕
1/8

BFS: layer by layer, with a queue

Breadth-first search (BFS) visits the start's neighbors first, then their neighbors, and so on, like ripples from a stone in water. It uses a queue: whoever is discovered first is visited first.

Since it moves in layers, the first time it reaches a vertex it does so along the path with the fewest edges. That's why BFS gives the distance in hops from the start. The only thing to watch is not adding anyone twice: mark them when you discover them.

It costs O(V + E): each vertex goes in once and each edge is looked at once per end.

ABCDEF
leccion.js

$ node leccion.js

Press RUN (or Ctrl+Enter).

What to look at

  • First A, then its layer (B and C), then the next one (D and E) and finally F.
  • F is 3 hops away: A → B → D → F or A → C → E → F, either one.
  • The cola array is never emptied: at the end it's the order everything was visited in.
The whole lesson on one page

BFS: layer by layer, with a queue

Breadth-first search (BFS) visits the start's neighbors first, then their neighbors, and so on, like ripples from a stone in water. It uses a queue: whoever is discovered first is visited first.

Since it moves in layers, the first time it reaches a vertex it does so along the path with the fewest edges. That's why BFS gives the distance in hops from the start. The only thing to watch is not adding anyone twice: mark them when you discover them.

It costs O(V + E): each vertex goes in once and each edge is looked at once per end.

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

function bfs(inicio) {
  const dist = { [inicio]: 0 };   // discovered = already has a distance
  const cola = [inicio];
  let cabeza = 0;                  // dequeue with an index: shift() is O(n)
  while (cabeza < cola.length) {
    const v = cola[cabeza++];
    for (const w of ady[v]) {
      if (!(w in dist)) {
        dist[w] = dist[v] + 1;
        cola.push(w);
      }
    }
  }
  console.log("visit order:", cola);
  return dist;
}

console.log(bfs("A"));
  • First A, then its layer (B and C), then the next one (D and E) and finally F.
  • F is 3 hops away: A → B → D → F or A → C → E → F, either one.
  • The cola array is never emptied: at the end it's the order everything was visited in.

DFS: all the way down, and back

Depth-first search (DFS) goes down one path until it can't continue, then backs up to try the next. It's the preorder walk from trees, but marking what was visited, because a graph has cycles and it would go around forever.

You write it with recursion (the call stack does the work) or with an explicit stack. It doesn't give distances, but it's great for anything like "what can I reach from here?". For example, counting components: the disconnected pieces of the graph. Each DFS that starts from an unvisited vertex discovers a whole component.

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

const visto = new Set();
const orden = [];
function dfs(v) {
  visto.add(v);
  orden.push(v);
  for (const w of ady[v]) if (!visto.has(w)) dfs(w);
}
dfs("A");
console.log("DFS from A:", orden);

// Three pieces: P-Q-R, S-T and U alone
const red = { P: ["Q"], Q: ["P", "R"], R: ["Q"], S: ["T"], T: ["S"], U: [] };

function componentes(g) {
  const visto = new Set();
  let cuenta = 0;
  for (const inicio in g) {
    if (visto.has(inicio)) continue;
    cuenta++;                      // nobody reached it: a new piece
    const pila = [inicio];         // DFS with an explicit stack
    visto.add(inicio);
    while (pila.length > 0) {
      const v = pila.pop();
      for (const w of g[v]) if (!visto.has(w)) { visto.add(w); pila.push(w); }
    }
  }
  return cuenta;
}
console.log("components:", componentes(red));
  • DFS from A goes A → B → D → C → E → F: it dives through B all the way before touching C as A's neighbor. BFS, instead, visited B and C together.
  • red has 3 components; U on its own counts as one.

A map is a graph too

A grid (a board, a tile map) is a graph even if nobody draws it that way: each square is a vertex and its neighbors above, below, left and right are its edges. No need to build an adjacency list: neighbors are computed by adding [1, 0], [-1, 0], [0, 1] and [0, -1].

The classic problem is counting islands: on a map of 1 (land) and 0 (water), how many groups of land there are. They're the components of the land graph. Daily Challenge's Snake does something similar to check that a new wall doesn't split the arena in two.

1100011010000110000001100
  • 0 water
  • 1 land
const mapa = [
  "11000",
  "11010",
  "00011",
  "00000",
  "01100",
];

function contarIslas(mapa) {
  const filas = mapa.length, cols = mapa[0].length;
  const visto = mapa.map(() => new Array(cols).fill(false));
  let islas = 0;
  for (let y = 0; y < filas; y++) {
    for (let x = 0; x < cols; x++) {
      if (mapa[y][x] !== "1" || visto[y][x]) continue;
      islas++;                                 // land nobody visited yet
      const cola = [[y, x]];                   // BFS from here
      visto[y][x] = true;
      let cabeza = 0;
      while (cabeza < cola.length) {
        const [cy, cx] = cola[cabeza++];
        for (const [dy, dx] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
          const ny = cy + dy, nx = cx + dx;
          if (ny < 0 || ny >= filas || nx < 0 || nx >= cols) continue;
          if (mapa[ny][nx] === "1" && !visto[ny][nx]) {
            visto[ny][nx] = true;
            cola.push([ny, nx]);
          }
        }
      }
    }
  }
  return islas;
}

console.log(contarIslas(mapa));

It gives 3: the top-left square, the "L" on the right (diagonal squares don't count as neighbors, but those touch side by side) and the one at the bottom. Change a 0 on the map to 1 to join two islands and run it.

Practice with a video challenge