Breadth-First Search (BFS)

Breadth-First Search is a graph traversal algorithm that explores all neighbors at the current depth level before moving on to nodes at the next depth level. Think of it as spreading outward in waves — like dropping a stone in water and watching the ripples expand ring by ring.

How BFS Works

BFS uses a queue (FIFO — First In, First Out) as its core data structure. Starting from a source node, it visits every neighbor at distance 1, then every neighbor at distance 2, and so on. A visited set prevents revisiting nodes and avoids infinite loops in cyclic graphs.

Start at the source node. Mark it visited and enqueue it.
Dequeue the front node. Process it.
Enqueue all unvisited neighbors of the current node, marking each visited.
Repeat steps 2–3 until the queue is empty.

Visual Walkthrough

Consider this undirected graph with 6 nodes. We run BFS starting from node A:

Core BFS Implementation

Here is a clean BFS implementation on an adjacency list in JavaScript:

/**
 * BFS on an adjacency list (undirected or directed graph)
 * @param {Map<string|number, Array>} graph - adjacency list
 * @param {string|number} start - starting node
 * @returns {Array} nodes in BFS traversal order
 */
function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];       // Use array as queue; shift() dequeues from front
  const order = [];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift(); // Dequeue front element — O(n) but fine for demos
    order.push(node);

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);   // Mark BEFORE enqueuing to prevent duplicates
        queue.push(neighbor);
      }
    }
  }

  return order;
}

// Build the example graph
const graph = new Map([
  ['A', ['B', 'C']],
  ['B', ['A', 'D', 'E']],
  ['C', ['A', 'E']],
  ['D', ['B']],
  ['E', ['B', 'C', 'F']],
  ['F', ['E']],
]);

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

Note

Mark nodes as visited when you **enqueue** them, not when you dequeue them. If you wait until dequeue, the same node can be added to the queue multiple times by different neighbors, causing redundant work or infinite loops.

Shortest Path with BFS

BFS guarantees the shortest path in an unweighted graph because it explores nodes level by level. The first time BFS reaches a destination, it has found the minimum number of edges needed to get there.

/**
 * Find shortest path between two nodes in an unweighted graph
 * Returns the path as an array of nodes, or null if unreachable
 */
function shortestPath(graph, start, end) {
  if (start === end) return [start];

  const visited = new Set([start]);
  // Store [currentNode, pathSoFar] in the queue
  const queue = [[start, [start]]];

  while (queue.length > 0) {
    const [node, path] = queue.shift();

    for (const neighbor of graph.get(node) || []) {
      if (neighbor === end) {
        return [...path, neighbor]; // Found! Return complete path
      }
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }

  return null; // No path exists
}

// Find shortest path from A to F
const path = shortestPath(graph, 'A', 'F');
console.log(path); // ['A', 'B', 'E', 'F'] — length 3

// Find shortest distance only (more memory-efficient)
function shortestDistance(graph, start, end) {
  if (start === end) return 0;

  const visited = new Set([start]);
  const queue = [[start, 0]]; // [node, distance]

  while (queue.length > 0) {
    const [node, dist] = queue.shift();

    for (const neighbor of graph.get(node) || []) {
      if (neighbor === end) return dist + 1;
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }

  return -1; // Unreachable
}

BFS on a Grid / Matrix

Many real problems use a 2D grid as the graph. Each cell is a node and its up/down/left/right neighbors are edges. BFS on grids works identically — just replace the adjacency list with boundary-checked neighbor generation.

/**
 * BFS on a 2D grid
 * Finds shortest path from start cell to end cell
 * '.' = open, '#' = wall
 */
function bfsGrid(grid, startRow, startCol, endRow, endCol) {
  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[0,1],[0,-1],[1,0],[-1,0]]; // right, left, down, up

  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  visited[startRow][startCol] = true;

  const queue = [[startRow, startCol, 0]]; // [row, col, distance]

  while (queue.length > 0) {
    const [r, c, dist] = queue.shift();

    if (r === endRow && c === endCol) return dist;

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;

      if (
        nr >= 0 && nr < rows &&    // in bounds
        nc >= 0 && nc < cols &&    // in bounds
        grid[nr][nc] !== '#' &&    // not a wall
        !visited[nr][nc]           // not yet visited
      ) {
        visited[nr][nc] = true;
        queue.push([nr, nc, dist + 1]);
      }
    }
  }

  return -1; // No path
}

const grid = [
  ['.', '.', '#', '.'],
  ['.', '#', '.', '.'],
  ['.', '.', '.', '#'],
  ['#', '.', '.', '.'],
];

console.log(bfsGrid(grid, 0, 0, 3, 3)); // 6

Time and Space Complexity

Metric	BFS	Notes
Time	O(V + E)	Every vertex and edge is visited at most once
Space	O(V)	Queue holds at most O(V) nodes; visited set is O(V)
Shortest path	Guaranteed	Only for unweighted graphs
Completeness	Yes	Will always find a path if one exists

Problem 1: Number of Islands (LeetCode 200)

Given an m x n grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Strategy: Iterate every cell. When you find unvisited land ('1'), increment the island count and BFS to mark the entire island as visited.

function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  let islands = 0;

  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

  function bfs(r, c) {
    const queue = [[r, c]];
    visited[r][c] = true;

    while (queue.length > 0) {
      const [cr, cc] = queue.shift();

      for (const [dr, dc] of dirs) {
        const nr = cr + dr;
        const nc = cc + dc;

        if (
          nr >= 0 && nr < rows &&
          nc >= 0 && nc < cols &&
          grid[nr][nc] === '1' &&
          !visited[nr][nc]
        ) {
          visited[nr][nc] = true;
          queue.push([nr, nc]);
        }
      }
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1' && !visited[r][c]) {
        islands++;
        bfs(r, c);
      }
    }
  }

  return islands;
}

// Example
const grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1'],
];
console.log(numIslands(grid)); // 3

// Time: O(M*N)  Space: O(M*N)

Problem 2: Rotten Oranges (LeetCode 994)

Each cell is 0 (empty), 1 (fresh orange), or 2 (rotten). Every minute, rotten oranges spread to adjacent fresh ones. Return the minimum minutes to rot all oranges, or -1 if impossible. Strategy: Multi-source BFS — start with ALL rotten oranges in the queue simultaneously. Each level of BFS represents one minute passing.

function orangesRotting(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  const queue = [];
  let fresh = 0;

  // Seed queue with all initially rotten oranges
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c, 0]); // [row, col, time]
      if (grid[r][c] === 1) fresh++;
    }
  }

  let maxTime = 0;

  while (queue.length > 0) {
    const [r, c, time] = queue.shift();

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;

      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
        grid[nr][nc] = 2;   // Mark as rotten
        fresh--;
        maxTime = Math.max(maxTime, time + 1);
        queue.push([nr, nc, time + 1]);
      }
    }
  }

  return fresh === 0 ? maxTime : -1;
}

console.log(orangesRotting([[2,1,1],[1,1,0],[0,1,1]])); // 4
console.log(orangesRotting([[2,1,1],[0,1,1],[1,0,1]])); // -1 (isolated orange)

// Time: O(M*N)  Space: O(M*N)

Problem 3: Word Ladder (LeetCode 127)

Given two words beginWord and endWord and a dictionary wordList, find the length of the shortest transformation sequence where each step changes exactly one letter and every intermediate word must be in wordList. Strategy: BFS on an implicit graph where each word is a node and edges connect words that differ by exactly one letter.

function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;

  const queue = [[beginWord, 1]]; // [currentWord, transformations]
  const visited = new Set([beginWord]);

  while (queue.length > 0) {
    const [word, steps] = queue.shift();

    // Try changing each character position
    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {           // a-z
        const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);

        if (newWord === endWord) return steps + 1;

        if (wordSet.has(newWord) && !visited.has(newWord)) {
          visited.add(newWord);
          queue.push([newWord, steps + 1]);
        }
      }
    }
  }

  return 0; // No valid sequence
}

console.log(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog']));
// 5  =>  hit -> hot -> dot -> dog -> cog

// Time: O(M^2 * N) where M = word length, N = wordList size
// Space: O(M^2 * N)

Problem 4: 01 Matrix (LeetCode 542)

Given a binary matrix, return a matrix where each cell contains the distance to the nearest 0. Strategy: Multi-source BFS starting from all 0 cells simultaneously. The distance propagates outward to 1 cells.

function updateMatrix(mat) {
  const rows = mat.length;
  const cols = mat[0].length;
  const dist = Array.from({ length: rows }, () => new Array(cols).fill(Infinity));
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  const queue = [];

  // Seed all zero cells with distance 0
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (mat[r][c] === 0) {
        dist[r][c] = 0;
        queue.push([r, c]);
      }
    }
  }

  while (queue.length > 0) {
    const [r, c] = queue.shift();

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;

      if (
        nr >= 0 && nr < rows &&
        nc >= 0 && nc < cols &&
        dist[nr][nc] > dist[r][c] + 1
      ) {
        dist[nr][nc] = dist[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }

  return dist;
}

const mat = [[0,0,0],[0,1,0],[1,1,1]];
console.log(updateMatrix(mat));
// [[0,0,0],
//  [0,1,0],
//  [1,2,1]]

// Time: O(M*N)  Space: O(M*N)

Problem 5: Minimum Steps to Reach Target

A knight on an n x n chessboard starts at position [0, 0]. Find the minimum number of moves to reach a target position [targetRow, targetCol]. Strategy: BFS from the start position, exploring all 8 knight moves at each step.

function minKnightMoves(n, targetRow, targetCol) {
  // All 8 possible knight moves
  const moves = [
    [-2,-1],[-2,1],[-1,-2],[-1,2],
    [1,-2],[1,2],[2,-1],[2,1]
  ];

  const visited = new Set();
  const start = `0,0`;
  const target = `${targetRow},${targetCol}`;

  if (start === target) return 0;

  visited.add(start);
  const queue = [[0, 0, 0]]; // [row, col, steps]

  while (queue.length > 0) {
    const [r, c, steps] = queue.shift();

    for (const [dr, dc] of moves) {
      const nr = r + dr;
      const nc = c + dc;

      if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;

      const key = `${nr},${nc}`;

      if (key === target) return steps + 1;

      if (!visited.has(key)) {
        visited.add(key);
        queue.push([nr, nc, steps + 1]);
      }
    }
  }

  return -1; // Unreachable
}

console.log(minKnightMoves(8, 5, 5)); // 4
// (0,0) -> (1,2) -> (3,3) -> (4,5) -> (5,5)... one of many optimal paths

// Time: O(N^2)  Space: O(N^2)

BFS Complexity Summary

Problem	Time	Space	Key Insight
Graph traversal	O(V+E)	O(V)	Visit every node/edge once
Shortest path (unweighted)	O(V+E)	O(V)	First reach = shortest path
Number of Islands	O(M*N)	O(M*N)	Flood-fill each island
Rotten Oranges	O(M*N)	O(M*N)	Multi-source BFS
Word Ladder	O(M²*N)	O(M²*N)	Implicit graph on words
01 Matrix	O(M*N)	O(M*N)	Multi-source from zeros

Tip

For large grids, use a proper deque (or index-based queue) instead of `array.shift()` to avoid O(n) dequeue cost. In competitive programming, a two-array swap technique or a pointer-based queue achieves true O(1) dequeue.

When to Use BFS vs DFS

Use BFS when...	Use DFS when...
You need the shortest path (unweighted)	You need to explore all paths
The answer is close to the source node	The graph is very deep or tree-like
You need level-by-level processing	You need topological sort
Multi-source propagation (rotten oranges)	You need backtracking (combinatorics)

Warning

BFS can use significantly more memory than DFS for wide graphs, since the queue may hold an entire level of nodes. For graphs with very high branching factors, DFS (or iterative deepening DFS) may be more practical.