What does the BFS algorithm do on graphs (Breadth-First Search)?

AlgorithmsJunior~3 min read

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.

Initialize distances as infinity, parents as null.
Put the start vertex into the queue, its distance = 0.
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.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.