Breadth-First Search (BFS): Queue-Based Graph Traversal

Breadth-First Search (BFS) explores a graph level by level: it visits the start vertex, then all of its neighbors, then all of their unvisited neighbors, and so on. It uses a queue (first-in, first-out) to remember what to visit next. BFS runs in O(V + E) time and is the go-to algorithm for finding the shortest path in an unweighted graph.

How BFS works

Put the start vertex in a queue and mark it visited.
Pop the front vertex, process it, and push every unvisited neighbor (marking each visited as you enqueue it).
Repeat until the queue is empty.

Because vertices come off the queue in the order they were discovered, BFS expands outward in rings of equal distance from the start.

#include <vector>
#include <queue>

std::vector<int> bfs(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<int> order;
    std::vector<bool> visited(adj.size(), false);
    std::queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;   // mark when enqueuing
                q.push(v);
            }
        }
    }
    return order;
}

List<Integer> bfs(List<List<Integer>> adj, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] visited = new boolean[adj.size()];
    Queue<Integer> q = new ArrayDeque<>();
    q.add(start);
    visited[start] = true;
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                visited[v] = true;   // mark when enqueuing
                q.add(v);
            }
        }
    }
    return order;
}

function bfs(adj, start) {
  const order = [];
  const visited = new Array(adj.length).fill(false);
  const queue = [start];
  visited[start] = true;
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];      // dequeue via moving index
    order.push(u);
    for (const v of adj[u]) {
      if (!visited[v]) {
        visited[v] = true;        // mark when enqueuing
        queue.push(v);
      }
    }
  }
  return order;
}

from collections import deque

def bfs(adj, start):
    order = []
    visited = [False] * len(adj)
    q = deque([start])
    visited[start] = True
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True   # mark when enqueuing
                q.append(v)
    return order

Pitfall: Mark a vertex visited when you enqueue it, not when you dequeue it. Marking on dequeue lets the same vertex be added many times, blowing up to O(V·E) or worse.

Shortest path in an unweighted graph

Because BFS reaches every vertex by the fewest possible edges, you get shortest distances for free — just record the distance to each neighbor as one more than the current vertex.

std::vector<int> bfsDistances(const std::vector<std::vector<int>>& adj, int start) {
    std::vector<int> dist(adj.size(), -1);
    std::queue<int> q;
    q.push(start); dist[start] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist;   // -1 means unreachable
}

int[] bfsDistances(List<List<Integer>> adj, int start) {
    int[] dist = new int[adj.size()];
    Arrays.fill(dist, -1);
    Queue<Integer> q = new ArrayDeque<>();
    q.add(start); dist[start] = 0;
    while (!q.isEmpty()) {
        int u = q.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.add(v);
            }
        }
    }
    return dist;   // -1 means unreachable
}

function bfsDistances(adj, start) {
  const dist = new Array(adj.length).fill(-1);
  const queue = [start];
  dist[start] = 0;
  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];
    for (const v of adj[u]) {
      if (dist[v] === -1) {
        dist[v] = dist[u] + 1;
        queue.push(v);
      }
    }
  }
  return dist;   // -1 means unreachable
}

from collections import deque

def bfs_distances(adj, start):
    dist = [-1] * len(adj)
    q = deque([start])
    dist[start] = 0
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist   # -1 means unreachable

Complexity and when to use it

Time: O(V + E) — each vertex and edge is examined once.
Space: O(V) for the visited array and the queue.

Use BFS for shortest paths in unweighted graphs, level-order problems (like word ladder), and finding connected components. For weighted shortest paths you need Dijkstra; to go deep instead of wide, use DFS.