Suggest an edit

Improve this article

Refine the answer for “What does the BFS algorithm do on graphs (Breadth-First Search)?”. 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

BFS (Breadth-First Search) is a graph traversal in breadth: it visits vertices layer by layer from the start vertex, first all its neighbors, then their neighbors, and so on. It uses a queue, finds shortest paths by number of edges in unweighted graphs, builds a level tree (parents/distances), and runs in O(V+E).

## Detailed answer

### Idea of the algorithm

BFS traverses the graph in layers (levels) relative to the start vertex. A queue is used to control the visiting order: vertices of the current level are processed first, then the next level.

1. Initialize distances as infinity, parents as null.
2. Put the start vertex into the queue, its distance = 0.
3. While the queue is not empty: dequeue a vertex u and for every neighbor w that is not yet visited, set dist[w] = dist[u] + 1, parent[w] = u, and add w to the queue.

### Properties and guarantees

- Guarantees shortest paths by number of edges in unweighted graphs (or graphs with equal weights).
- Builds a BFS tree: for every reached vertex, the parent and the level (distance) are known.
- Works correctly for both directed and undirected graphs (in the directed case, edge directions are taken into account).
- Neighbor order affects which specific shortest path is found, but not its length (if several paths of the same length exist, one of them is returned).

### Complexity

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

### Pseudocode

```text
BFS(G, s):
  for v in V(G):
    dist[v] = INF
    parent[v] = null
  dist[s] = 0
  Q = queue()
  Q.enqueue(s)

while not Q.empty():
    u = Q.dequeue()
    for w in adj[u]:
      if dist[w] == INF:        # w not yet visited
        dist[w] = dist[u] + 1
        parent[w] = u
        Q.enqueue(w)

# After running:
# dist[v] - the length of the shortest path by edges from s to v (or INF if unreachable)
# parent[v] - the predecessor of v in the BFS tree (for path reconstruction)
```

### Implementation in JavaScript/TypeScript

```typescript
type Graph = Record<string, string[]>;

function bfs(graph: Graph, start: string) {
  const dist: Record<string, number> = {};
  const parent: Record<string, string | null> = {};

for (const v in graph) {
    dist[v] = Infinity;
    parent[v] = null;
  }

const queue: string[] = [];
  let head = 0; // pointer to the head of the queue for O(1) dequeue

dist[start] = 0;
  queue.push(start);

while (head < queue.length) {
    const u = queue[head++];
    for (const w of graph[u]) {
      if (dist[w] === Infinity) { // not visited
        dist[w] = dist[u] + 1;
        parent[w] = u;
        queue.push(w);
      }
    }
  }

return { dist, parent };
}

function reconstructPath(parent: Record<string, string | null>, target: string) {
  const path: string[] = [];
  let cur: string | null = target;
  while (cur !== null) {
    path.push(cur);
    cur = parent[cur];
  }
  path.reverse();
  return path;
}

// Example usage
const graph: Graph = {
  A: ["B", "C"],
  B: ["A", "D", "E"],
  C: ["A", "F"],
  D: ["B"],
  E: ["B", "F"],
  F: ["C", "E"],
};

const { dist, parent } = bfs(graph, "A");
console.log(dist["F"]); // 2, the shortest number of edges A->F
console.log(reconstructPath(parent, "F")); // For example: [ 'A', 'C', 'F' ] (one of the shortest paths)
```

### Example on a graph

Let the start be vertex A. The levels (distances) will be:

- Level 0: A
- Level 1: B, C (neighbors of A)
- Level 2: D, E, F (neighbors of B and C, not yet visited)

Hence the distance to F equals 2 (for example, the path A → C → F). If several shortest paths exist, BFS returns the one that arose first based on the order of neighbors in the adjacency list.

### Applications

- Finding the shortest path in unweighted graphs and on grids (mazes).
- Checking connectivity, finding connected components (running BFS from every unvisited vertex).
- Checking whether a graph is bipartite (two-coloring by level).
- Computing levels/layers in a graph, building a BFS tree.
- Topological sorting with Kahn's algorithm (a BFS variant based on in-degrees for a DAG).

### Variations

- Multi-source BFS: several starting vertices with dist=0 are put into the queue initially. Useful when you need the distance from any of the sources.
- Bidirectional BFS: simultaneous traversal from the source and the target, speeds up shortest-path search in large sparse graphs.
- 0-1 BFS: an extension for edges with weights 0 and 1 (uses a deque instead of a queue).

### Frequent mistakes

- Marking a vertex visited only on dequeue, which can lead to the same node being added multiple times. It is correct to mark it when enqueuing.
- Applying BFS to graphs with arbitrary positive weights as if they were unweighted, the paths will not be optimal (Dijkstra is needed).
- Forgetting to account for edge direction in a directed graph.
- Incorrect distance initialization (for example, 0 instead of infinity for unvisited vertices).

### When it doesn't fit

- A graph with arbitrary non-negative weights, use Dijkstra (or 0-1 BFS for weights 0/1).
- Negative weights, the Bellman-Ford/SPFA algorithms.
- Very dense or huge graphs can run into memory/time limits because of the storage needed for the queue and adjacency lists.

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.