Breadth-First Search (BFS) Algorithm Tutorial

What Is Breadth-First Search (BFS)?

Breadth-First Search, commonly called BFS, is a graph traversal algorithm that visits vertices level by level. Starting from a selected vertex, BFS first visits all directly connected neighbors before moving to vertices that are farther away.

BFS uses a queue to maintain the order in which vertices should be processed. This makes it particularly useful when you need to explore a graph by distance or find the shortest path in an unweighted graph.

Core idea: Visit the starting vertex, add its unvisited neighbors to a queue, process the queue from front to back, and continue until there are no vertices left to visit.

How BFS Traverses a Graph

Consider a graph where A is connected to B and C, while B is connected to D and C is connected to E.

If BFS starts at A, the traversal is:

Visit A.
Add B and C to the queue.
Process B and discover D.
Process C and discover E.
Process D.
Process E.

The resulting traversal is A → B → C → D → E. Notice that vertices at the same distance from the starting point are processed before deeper vertices.

BFS Uses a Queue

A queue follows the First In, First Out (FIFO) principle. The vertex that is discovered first is processed first.

During BFS, the queue typically changes like this:

Step	Action	Queue
1	Start at A	A
2	Process A, add B and C	B, C
3	Process B, add D	C, D
4	Process C, add E	D, E
5	Process D	E
6	Process E	Empty

The BFS Algorithm

A standard BFS implementation follows a small number of important steps:

Create an empty queue.
Create a collection to track visited vertices.
Mark the starting vertex as visited.
Add the starting vertex to the queue.
Remove a vertex from the front of the queue.
Process that vertex.
Add each unvisited neighbor to the queue and mark it as visited.
Repeat until the queue becomes empty.

Marking a vertex as visited when it is added to the queue is important. It prevents the same vertex from being inserted multiple times when several vertices point to it.

BFS Implementation in JavaScript

An adjacency list is a convenient representation for implementing BFS. A JavaScript Map can store each vertex and its neighboring vertices.

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

  let front = 0;

  while (front < queue.length) {
    const current = queue[front++];
    result.push(current);

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

  return result;
}

const graph = new Map([
  ['A', ['B', 'C']],
  ['B', ['A', 'D']],
  ['C', ['A', 'E']],
  ['D', ['B']],
  ['E', ['C']]
]);

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

The front variable acts as the queue pointer. Using an index instead of repeatedly calling shift() avoids repeatedly moving the remaining elements of a JavaScript array.

BFS with an Adjacency List

The adjacency list is commonly used with BFS because it allows the algorithm to iterate directly over the neighbors of each visited vertex.

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

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

  let index = 0;

  while (index < queue.length) {
    const node = queue[index++];
    order.push(node);

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

  return order;
}

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

Why Do We Need a Visited Set?

Graphs can contain cycles. Without a visited collection, BFS could repeatedly process the same vertices.

A → B
↑   ↓
└── C

Starting from A, the algorithm reaches B, then C, and then encounters A again. The visited set tells BFS that A has already been processed or scheduled for processing.

A good BFS implementation therefore follows this rule: mark a vertex visited when you enqueue it, not when you remove it.

BFS Level-by-Level Traversal

One of BFS's defining properties is that it naturally processes vertices by their distance from the starting vertex. This is often called level-order traversal.

Level 0: A
Level 1: B, C
Level 2: D, E

This property makes BFS useful for problems where the question involves the minimum number of edges, moves, or steps required to reach another vertex.

Finding the Shortest Path in an Unweighted Graph

BFS can find the shortest path from a starting vertex to other vertices when every edge has the same cost, such as an unweighted graph where each edge represents one step.

The key idea is to store the distance of each vertex from the starting point. When BFS first discovers a vertex, the distance assigned to it is the minimum number of edges needed to reach it.

function bfsDistances(graph, start) {
  const queue = [start];
  const distance = new Map([[start, 0]]);

  let front = 0;

  while (front < queue.length) {
    const current = queue[front++];

    for (const neighbor of graph.get(current) || []) {
      if (!distance.has(neighbor)) {
        distance.set(neighbor, distance.get(current) + 1);
        queue.push(neighbor);
      }
    }
  }

  return distance;
}

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

console.log(bfsDistances(graph, 'A'));
// A: 0
// B: 1
// C: 1
// D: 2
// E: 2
// F: 3

Reconstructing a Shortest Path with BFS

BFS can also record the previous vertex used to reach each newly discovered vertex. This allows the actual shortest path to be reconstructed after the search finishes.

function shortestPath(graph, start, target) {
  const queue = [start];
  const visited = new Set([start]);
  const previous = new Map();

  let front = 0;

  while (front < queue.length) {
    const current = queue[front++];

    if (current === target) {
      break;
    }

    for (const neighbor of graph.get(current) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        previous.set(neighbor, current);
        queue.push(neighbor);
      }
    }
  }

  if (!visited.has(target)) {
    return [];
  }

  const path = [];
  let current = target;

  while (current !== undefined) {
    path.push(current);
    current = previous.get(current);
  }

  return path.reverse();
}

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

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

BFS on a Grid

A grid can also be treated as a graph. Each cell represents a vertex, while movement between neighboring cells represents an edge.

BFS is especially useful for finding the minimum number of moves between cells when every movement has the same cost.

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

// S = start
// T = target
// # = blocked cell
// . = walkable cell

From each cell, BFS can attempt to move up, down, left, and right. A visited structure prevents the algorithm from returning to cells that have already been explored.

BFS for a Grid Shortest-Path Problem

The following example calculates the minimum number of moves from the top-left cell to the bottom-right cell while avoiding blocked cells.

function shortestGridPath(grid) {
  const rows = grid.length;
  const cols = grid[0].length;

  const queue = [[0, 0, 0]];
  const visited = new Set(['0,0']);

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

  let front = 0;

  while (front < queue.length) {
    const [row, col, distance] = queue[front++];

    if (row === rows - 1 && col === cols - 1) {
      return distance;
    }

    for (const [dr, dc] of directions) {
      const nextRow = row + dr;
      const nextCol = col + dc;

      if (
        nextRow >= 0 &&
        nextRow < rows &&
        nextCol >= 0 &&
        nextCol < cols &&
        grid[nextRow][nextCol] !== '#' &&
        !visited.has(`${nextRow},${nextCol}`)
      ) {
        visited.add(`${nextRow},${nextCol}`);
        queue.push([nextRow, nextCol, distance + 1]);
      }
    }
  }

  return -1;
}

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

console.log(shortestGridPath(grid));
// 4

BFS on a Tree

A tree is a special type of graph, so BFS can also be used to traverse a tree. In tree terminology, this is commonly called level-order traversal.

        1
       / \
      2   3
     / \   \
    4   5   6

BFS:
1 → 2 → 3 → 4 → 5 → 6

Unlike a general graph, a tree does not contain cycles when represented as a standard rooted tree. However, a visited structure can still be useful when working with tree-like data represented as a general graph.

BFS vs DFS

Breadth-First Search and Depth-First Search are both fundamental graph traversal algorithms, but they explore the graph in different ways.

Feature	BFS	DFS
Main structure	Queue	Stack or recursion
Traversal style	Level by level	Depth first
Shortest path in unweighted graph	Yes	Not guaranteed
Typical memory behavior	Can hold a wide frontier	Can follow a deep path
Common applications	Shortest paths, levels, nearest nodes	Backtracking, cycle detection, components

BFS Time and Space Complexity

For a graph represented using an adjacency list, BFS visits each reachable vertex and examines each relevant edge.

Time complexity: O(V + E)
Space complexity: O(V)

Here, V represents the number of vertices and E represents the number of edges.

The O(V) auxiliary space comes from structures such as the queue and visited set. If the graph is represented using an adjacency matrix, examining neighbors can require O(V) work for each processed vertex, resulting in O(V²) traversal time.

When Should You Use BFS?

BFS is a strong choice when the problem naturally involves levels, minimum numbers of unweighted steps, or exploring nearby vertices before distant ones.

Finding the shortest path in an unweighted graph.
Finding the minimum number of moves in a grid.
Finding vertices within a certain distance.
Level-order traversal of trees.
Finding the nearest reachable resource or node.
Checking reachability from a starting vertex.
Exploring social-network connections by degrees of separation.
Processing systems where tasks are naturally grouped into levels.

BFS and Shortest Paths: An Important Limitation

BFS finds shortest paths based on the number of edges, not the total weight of edges. Therefore, it should not automatically be used for every weighted graph.

A --1--> B
|         |
5         1
|         |
v         v
C --1--> D

If edge weights represent travel cost, distance, or time, the path with fewer edges is not necessarily the path with the lowest total cost. For graphs with non-negative edge weights, Dijkstra's algorithm is commonly used instead.

Common BFS Mistakes

1. Forgetting the Visited Set

Cyclic graphs can cause repeated processing or even an infinite traversal if visited vertices are not tracked.

2. Marking Nodes Too Late

Mark vertices as visited when they are added to the queue. Waiting until they are removed can allow the same vertex to be queued multiple times.

3. Using Array.shift() for Large Queues

In JavaScript, repeatedly removing the first array element with shift() can cause unnecessary element movement. A front index provides a more efficient queue pattern for BFS.

4. Using BFS for Weighted Shortest Paths

Standard BFS assumes that every traversal step has equal cost. For weighted shortest-path problems, choose an algorithm based on the edge-weight constraints.

5. Assuming There Is Only One Valid BFS Order

The exact traversal order can depend on the order in which neighbors appear in the graph representation. Different neighbor orders can produce different but valid BFS traversals.

BFS in Real-World Applications

BFS is useful whenever relationships can be represented as a graph and nearby relationships should be examined before more distant ones.

Social networks: exploring connections by degrees of separation.
Maps and navigation: finding minimum-step routes when movement costs are equal.
Games: finding the minimum number of moves across a uniform-cost board.
Networking: exploring connected devices or communication paths.
Web crawling: exploring links level by level from a starting page.
Dependency analysis: processing graph structures by levels.
Grid problems: finding the nearest target or shortest route through a matrix.

BFS Interview Pattern

Many coding interview problems can be recognized as BFS problems when the question contains concepts such as minimum steps, shortest path, nearest, level by level, or fewest moves.

A useful approach is:

Identify the vertices or states.
Identify how one state can move to another.
Determine whether every move has equal cost.
Create a queue.
Track visited states.
Process states level by level.
Store distance or parent information if the problem requires it.

BFS vs Other Graph Algorithms

Problem	Common Approach
Unweighted shortest path	BFS
General graph traversal	BFS or DFS
Non-negative weighted shortest path	Dijkstra's algorithm
Negative edge weights	Bellman-Ford, depending on the problem
Dependency ordering	Topological sorting
Explore deeply / backtracking	DFS

Key Takeaways

BFS is a graph traversal algorithm that explores vertices level by level.
BFS uses a queue based on the FIFO principle.
A visited set prevents repeated processing and problems caused by cycles.
BFS finds shortest paths by number of edges in unweighted graphs.
BFS is useful for level-order traversal, grids, nearest-node problems, and minimum-step problems.
For an adjacency-list graph, BFS runs in O(V + E) time.
BFS is not the standard choice for weighted shortest paths where edge costs differ.
The order of neighbors can affect the exact traversal sequence.

Topics

Breadth-First Search (BFS) Algorithm