What does the queue do in BFS on graphs?

AlgorithmsJunior~3 min read

Short answer

The queue in BFS holds the "frontier", vertices that have been discovered but not yet processed, and dequeues them in FIFO order. This guarantees a layer-by-layer traversal (by increasing number of edges from the start) and, as a result, finds shortest paths in unweighted graphs.

Detailed answer

What does the queue do in BFS?

In the breadth-first search (BFS) algorithm, the queue is a data structure that enforces "first in, first out" (FIFO) processing order for vertices. As soon as a vertex is discovered, it is placed into the queue. When its turn comes, it is dequeued, and we "expand" its neighbors. This order produces a strict layer-by-layer scan of the graph: first all vertices at distance 1, then distance 2, and so on.

Why the queue is needed (main roles)

Holds the frontier: the set of vertices already found but not yet expanded.
Guarantees layer order: dequeued vertices never decrease in distance from the source.
Ensures correct shortest paths in unweighted graphs: the first visit to a vertex gives the minimal number of edges to it.
Helps avoid reprocessing: paired with visited, it prevents a vertex from being enqueued twice.

How BFS works step by step

Initialize visited, dist, parent. Put the start vertex s into the queue, mark visited[s] = true, dist[s] = 0.
While the queue is not empty: dequeue a vertex u from the head of the queue.
For every neighbor v of u: if v is not yet visited, mark visited[v] = true, dist[v] = dist[u] + 1, parent[v] = u, and add v to the tail of the queue.
Repeat until every reachable vertex is processed.

Key invariants of the queue

Vertices are dequeued in order of non-decreasing distance from the source.
Each vertex enters the queue at most once (if visited is marked on enqueue).
By the time u is dequeued, all vertices of the previous layer have already been dequeued and fully expanded.

Why a queue, and not a stack or a priority queue?

A stack (LIFO) turns the algorithm into DFS: it goes deep along a single path, and shortest paths are not guaranteed.
A priority queue changes the algorithm (Dijkstra), needed for weighted graphs with non-negative weights. That is no longer classic BFS.
A deque with pushFront turns the traversal into variations that break the layer property if used incorrectly.

Complexity

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

Frequent mistakes

Marking visited on dequeue instead of on enqueue, which leads to duplicates in the queue.
Using Array.shift() in JS, which is O(n); it is better to keep a head index.
Not resetting the structures between BFS runs.
Applying BFS to a weighted graph as if it were unweighted and expecting correct shortest paths, which is wrong.

Code example (JavaScript)

function bfs(adj, start) {
  const n = adj.length;
  const visited = Array(n).fill(false);
  const dist = Array(n).fill(Infinity);
  const parent = Array(n).fill(-1);

  // Queue with a head pointer (O(1) per operation)
  const queue = [];
  let head = 0;

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

  const order = []; // the order of dequeuing

  while (head < queue.length) {
    const u = queue[head++]; // dequeue
    order.push(u);

    for (const v of adj[u]) {
      if (!visited[v]) {
        visited[v] = true;           // Important: mark on enqueue
        dist[v] = dist[u] + 1;
        parent[v] = u;
        queue.push(v);               // enqueue
      }
    }
  }

  return { visited, dist, parent, order };
}

// Example graph (undirected), vertices: 0..4
// 0-1, 0-2, 1-3, 2-3, 3-4
const adj = [
  [1, 2],   // 0
  [0, 3],   // 1
  [0, 3],   // 2
  [1, 2, 4],// 3
  [3]       // 4
];

const { dist, parent, order } = bfs(adj, 0);
console.log('Dequeue order:', order);       // [0, 1, 2, 3, 4]
console.log('Distances from 0    :', dist);       // [0, 1, 1, 2, 3]

// Reconstructing the path 0 -> 4
function restorePath(parent, t) {
  const path = [];
  for (let v = t; v !== -1; v = parent[v]) path.push(v);
  return path.reverse();
}
console.log('Shortest path 0→4:', restorePath(parent, 4)); // [0,1,3,4] or [0,2,3,4]

Mini example: traversal levels

For the graph from the example, starting at 0, the queue produces the following levels:

Level 0: 0
Level 1: 1, 2
Level 2: 3
Level 3: 4

Useful variations

Multi-source: put all the starting vertices into the queue at once with dist = 0, to find the distance to the nearest source.
Early termination: you can stop as soon as the target vertex is dequeued, its dist is already minimal.
Bidirectional BFS: two queues, one from the source and one from the target, to speed things up on undirected graphs.

Short Answer

Interview ready

Premium

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