Breadth-First Search
What’s the fewest hops between two people? BFS explores a network ripple by ripple and finds the shortest unweighted path.
The problem
On a professional network, you want to know: how many introductions away is that hiring manager? A direct connection is one hop. A friend-of-a-friend is two. You don't care which chain — you care about the shortest one, because fewer hops means an easier introduction.
The people form a graph, and every edge is one hop — all edges cost the same. You need the minimum number of edges from you to the manager. Guessing a path and counting won't do; you might stumble onto a ten-hop chain when a three-hop one exists. You need a method that finds the shortest by construction.
A first attempt
You might explore greedily: walk to a neighbor, then that neighbor's neighbor, following one trail deep before trying another. But depth-first wandering can reach the target the long way first — it commits to a chain before checking closer people. When it finally arrives, the hop count isn't guaranteed minimal, so you'd have to explore every path and compare. On a large network that's exponential blowup.
The fix isn't cleverer trail-picking. It's changing the order in which you visit people.
The insight
Visit people in order of distance. First everyone 1 hop away, then everyone 2 hops away, then 3 — expanding outward in rings, like ripples from a stone dropped in water.
The moment a ring reaches the target, you're done: no closer ring contained it, so the current ring is its true distance. To enforce "closest first," process people in the exact order you discover them — first in, first out. That's a queue, and the whole technique is breadth-first search.
Why a queue, not a stack
A queue hands back the oldest waiting vertex, so all distance-1 vertices are processed before any distance-2 vertex is touched. Swap the queue for a stack and you get depth-first search — same skeleton, opposite order, and you lose the shortest-path guarantee.
How it works
Seed the queue with the start
Put the start vertex in the queue and mark it visited so you never enqueue it twice. Record its distance as 0.
Pop the front vertex
Take the oldest vertex off the queue. This is the current ripple's frontier.
Enqueue its unvisited neighbors
For each neighbor not yet visited: mark it visited, set its distance to dist[current] + 1,
and push it to the back. Marking when enqueuing (not when popping) prevents the same
vertex from entering the queue multiple times.
Repeat until the queue empties
Keep popping and expanding. Every vertex is dequeued exactly once, in nondecreasing order of distance. Stop early if you pop the target.
Starting BFS from 0 on this graph, the rings come out in order 0 | 1 2 | 3 4 5:
(1)---(3)
/ \
(0) (5)
\ /
(2)---(4)
queue: [0] visit 0 dist 0
[1,2] visit 1, 2 dist 1
[3,4] visit 3, 4 dist 2
[5] visit 5 dist 3The code
from collections import deque
def bfs(adj, start):
n = len(adj)
dist = [-1] * n # -1 = unvisited
dist[start] = 0
q = deque([start])
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
if dist[v] == -1: # mark on enqueue
dist[v] = dist[u] + 1
q.append(v)
return order, distfunction bfs(adj: number[][], start: number): { order: number[]; dist: number[] } {
const n = adj.length;
const dist = new Array(n).fill(-1);
dist[start] = 0;
const q: number[] = [start];
const order: number[] = [];
let head = 0;
while (head < q.length) {
const u = q[head++];
order.push(u);
for (const v of adj[u]) {
if (dist[v] === -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return { order, dist };
}import java.util.*;
int[] bfs(List<List<Integer>> adj, int start) {
int n = adj.size();
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[start] = 0;
Queue<Integer> q = new ArrayDeque<>();
q.add(start);
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;
}#include <string.h>
/* adj: adjacency list via arrays; deg[u] = neighbor count */
void bfs(int adj[][100], int deg[], int n, int start, int dist[]) {
memset(dist, -1, n * sizeof(int));
int queue[100000], head = 0, tail = 0;
dist[start] = 0;
queue[tail++] = start;
while (head < tail) {
int u = queue[head++];
for (int i = 0; i < deg[u]; i++) {
int v = adj[u][i];
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
queue[tail++] = v;
}
}
}
}#include <vector>
#include <queue>
std::vector<int> bfs(const std::vector<std::vector<int>>& adj, int start) {
int n = adj.size();
std::vector<int> dist(n, -1);
dist[start] = 0;
std::queue<int> q;
q.push(start);
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;
}Mark on enqueue, not on dequeue
If you only mark a vertex visited when you pop it, the same vertex can be pushed by
several neighbors before it's popped — the queue balloons and distances can be overwritten.
Always set dist[v] (or visited[v]) the instant you enqueue v.
Complexity
| Aspect | Cost | Why |
|---|---|---|
| Time | O(n + m) | each vertex dequeued once, each edge examined once |
| Space | O(n) | the queue plus the dist/visited array |
n is the vertex count and m the edge count. Every edge is looked at from each endpoint,
so with an adjacency list the total edge work is O(m).
When to use it
BFS shines here
Reach for BFS to find the shortest path in an unweighted graph (fewest edges), to explore level by level, to find connected components, or to test bipartiteness. It does not find shortest paths when edges have different weights — for that you need Dijkstra. When several starting points spread at once (fire, rot, signal), see Multi-Source BFS.
Practice
Recap
- BFS explores a graph in rings of increasing distance using a FIFO queue.
- The first time it reaches a vertex is along a shortest unweighted path — that's its signature guarantee.
- It runs in
O(n + m)time andO(n)space; always mark vertices visited on enqueue.
How is this guide?
Last updated on