Suggest an edit

Improve this article

Refine the answer for “What is Breadth-First Search (BFS)?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

Breadth-First Search (BFS) is an algorithm for traversing a graph/tree that visits vertices "layer by layer" from the starting vertex, using a queue. It guarantees finding the shortest path by edge count in unweighted graphs, and runs in O(V+E) time and O(V) memory.

## Detailed answer

### Definition

BFS is an algorithm that starts traversing from a given starting vertex and successively visits all vertices at distance 1 edge, then distance 2 edges, and so on. A queue (FIFO) controls the visit order. This "layered" traversal correctly measures the minimum number of edges from the source to every reachable vertex in an unweighted graph.

### Key idea

- Put the starting vertex into the queue, mark it as visited, and set its distance to 0.
- While the queue isn't empty: dequeue a vertex u from the front, "expand" it by going through all of its neighbors v.
- If a neighbor v isn't visited yet: mark it visited when adding it to the queue, record its parent v = u, set dist[v] = dist[u] + 1, and push v onto the back of the queue.

### Properties and guarantees

- Layering: vertices are visited in order of non-decreasing shortest distance from the source.
- Shortest paths in unweighted graphs: BFS finds the minimum number of edges from the source to every reachable vertex.
- Works for both directed and undirected graphs (respecting edge direction).
- Suits trees (it gives a level-order traversal).

### Complexity

- Time: O(V + E), where V is the number of vertices and E is the number of edges.
- Memory: O(V) for the queue and the dist/visited/parent arrays.

### Data structures

- A queue (FIFO), controlling the traversal order by level.
- visited, marking that a vertex has already been enqueued (important to mark it when adding, not when dequeuing).
- dist, the distance in edges from the source to a vertex.
- parent, a vertex's parent in the BFS tree, used to reconstruct the path.

### Pseudocode (JavaScript)

```
function bfs(adj, start) {
  const n = adj.length;
  const dist = Array(n).fill(Infinity);
  const parent = Array(n).fill(-1);
  const visited = Array(n).fill(false);
  const q = [];
  let head = 0; // implementing the queue with an array and a head pointer

q.push(start);
  visited[start] = true;
  dist[start] = 0;

while (head < q.length) {
    const u = q[head++];
    for (const v of adj[u]) {
      if (!visited[v]) {
        visited[v] = true;        // mark when adding
        parent[v] = u;            // remember the BFS tree
        dist[v] = dist[u] + 1;    // distance by layer
        q.push(v);
      }
    }
  }
  return { dist, parent, visited };
}
```

### Reconstructing the path (via parent)

After BFS, you can reconstruct the shortest path from s to t by walking up parent from t to s and reversing the sequence.

```
function getPath(parent, s, t) {
  const path = [];
  for (let v = t; v !== -1; v = parent[v]) path.push(v);
  path.reverse();
  return path[0] === s ? path : []; // if t is unreachable, return an empty path
}
```

### Example: shortest path in an undirected graph

The graph is given as adjacency lists. Let's find the shortest path from 0 to 5.

```
const adj = [
  /*0*/ [1, 2],
  /*1*/ [0, 3, 4],
  /*2*/ [0, 4],
  /*3*/ [1, 5],
  /*4*/ [1, 2, 5],
  /*5*/ [3, 4]
];

const { dist, parent } = bfs(adj, 0);
console.log('dist to 5:', dist[5]);          // 3
console.log('path 0->5:', getPath(parent, 0, 5)); // for example [0,1,3,5] or [0,2,4,5]
```

### Example: level-order tree traversal

For trees, BFS corresponds to a level-order traversal: first the root, then all nodes at depth 1, then depth 2, and so on.

```
class Node {
  constructor(val, left = null, right = null) {
    this.val = val; this.left = left; this.right = right;
  }
}

// Example tree:       1
//                    / \
//                   2   3
//                  / \   \
//                 4   5   6
const root = new Node(1, new Node(2, new Node(4), new Node(5)), new Node(3, null, new Node(6)));
console.log(levelOrder(root)); // [[1],[2,3],[4,5,6]]
```

### BFS on a grid: shortest path with obstacles

Cells with value 0 are walkable, 1 are obstacles. We move in 4 directions. BFS returns the length of the shortest path in steps.

```
function shortestPathGrid(grid, start, goal) {
  const m = grid.length, n = grid[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  const dist = Array.from({ length: m }, () => Array(n).fill(Infinity));
  const q = [];
  let head = 0;
  const [sx, sy] = start, [gx, gy] = goal;
  if (grid[sx][sy] === 1 || grid[gx][gy] === 1) return -1;

dist[sx][sy] = 0;
  q.push([sx, sy]);

while (head < q.length) {
    const [x, y] = q[head++];
    if (x === gx && y === gy) return dist[x][y];
    for (const [dx, dy] of dirs) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] === 0 && dist[nx][ny] === Infinity) {
        dist[nx][ny] = dist[x][y] + 1;
        q.push([nx, ny]);
      }
    }
  }
  return -1; // no path to the goal
}

const grid = [
  [0,0,1,0],
  [0,0,0,0],
  [1,0,1,0],
  [0,0,0,0]
];
console.log(shortestPathGrid(grid, [0,0], [3,3]));
```

### Variations and applications

- Shortest paths in unweighted graphs and grids (in steps/edges).
- Determining reachability and distances from the source to all vertices.
- Checking connectivity/counting connected components (running BFS from unvisited vertices).
- Checking bipartiteness: coloring by level (alternating colors).
- Multi-source BFS: starting from a set of vertices at once (distance 0), useful for "wave" propagation problems.

### BFS vs DFS

- BFS uses a queue and moves layer by layer; DFS uses a stack/recursion and goes deep.
- BFS finds the shortest path in unweighted graphs; DFS gives no such guarantee.
- Memory: BFS can consume more memory on wide levels; DFS is usually more memory-efficient.

### When BFS doesn't fit

- Weighted graphs with varying weights: Dijkstra's algorithm is needed (or 0-1 BFS for weights of 0/1, or A* with a heuristic).
- Very wide graphs/levels, causing high memory consumption.

### Common errors

- Marking visited too late (when dequeuing), which can let nodes end up in the queue multiple times.
- Using a stack instead of a queue, which gives DFS instead of BFS.
- Forgetting to initialize dist/parent/visited for each BFS run.
- Handling edge direction incorrectly in directed graphs.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts1122 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.