Breadth-First Search (BFS) Algorithm

BFS explores a graph like ripples in a pond. Drop a stone at the start node. First you visit everything one step away. Then two steps. Then three. Level by level, outward.

What It Does

BFS visits every node in a graph layer by layer. It uses a queue — first in, first out. This guarantees the shortest path in unweighted graphs.

That's the key property. If every edge has the same cost, BFS gives you the shortest path for free. DFS doesn't.

The Code

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

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

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}

console.log(bfs(graph, 'A'));
// ['A', 'B', 'C', 'D', 'E', 'F', 'G']

How It Works

1. Start at A. Mark it visited. Add it to the queue.
2. Dequeue A. Visit neighbors B and C. Add them to the queue.
3. Dequeue B. Visit neighbors D and E (skip A — already visited).
4. Dequeue C. Visit neighbors F and G.
5. Continue until the queue is empty.

Complexity

• Time: O(V + E) — you visit every vertex and traverse every edge once.
• Space: O(V) — the queue and visited set can hold all vertices.

When to Use BFS

• Shortest path in unweighted graphs.
• Level-order traversal of trees.
• Finding connected components.
• Web crawlers — explore pages layer by layer.

The Trade-off

BFS uses more memory than DFS because it stores entire levels in the queue. For a tree with branching factor b and depth d, BFS holds O(b^d) nodes in memory. DFS only holds O(d). If memory is tight and you don't need shortest path, DFS is the better choice.