Breadth-first search
easyEvery node at distance 1 is dequeued before any node at distance 2. Includes the single most common BFS bug: marking nodes on dequeue instead of on enqueue.
O(V + E)Space O(V)Saved in this browser - no sign-up, nothing sent anywhere.
How breadth-first search works
Breadth-first search explores a graph in rings. It visits the start, then everything one edge away, then everything two edges away - a queue enforces the order, because nodes discovered earlier are dequeued earlier. On the default 8-node graph, A comes off the queue first, then B and D at distance 1, then C, E and G at distance 2.
That ring discipline is the entire reason BFS finds shortest paths on unweighted graphs. The first time a node is discovered, it was reached through a node one ring closer, so its recorded distance can never be beaten. The distances along the queue never decrease - watch the d= labels in the visualizer.
Reach for BFS whenever every edge costs the same and you want fewest hops: shortest word-ladder chains, minimum moves in a puzzle, degrees of separation. The moment edges carry different weights, the ring argument collapses and you need Dijkstra - which is BFS with the queue swapped for a priority queue.
Step by step
- Start at A: mark it seen, set distance 0, enqueue it. The queue is the frontier - discovered but not yet processed.
- Dequeue A and scan its neighbours. B and D are new: mark both immediately, record distance 1, and push them to the back.
- Dequeue B (distance 1). A is already seen and gets skipped; C and E are marked at distance 2.
- Dequeue D. E is already marked - skipping it is what keeps the queue from growing without bound. Only G is new, at distance 2.
- Ring 2 drains: C discovers F at distance 3, E discovers H at distance 3, G finds nothing new.
- The queue empties after visiting all 8 nodes in order A, B, D, C, E, G, F, H. Every recorded distance is the true shortest hop count.
Complexity
| Worst case time | O(V + E) |
|---|---|
| Space | O(V) |
The queue holds at most two levels, so peak memory is the graph's width.
Reference implementation
Python
from collections import deque
def bfs(adj, start):
seen = {start}
dist = {start: 0}
q = deque([start])
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
if v not in seen:
seen.add(v) # mark when enqueued, not when visited -
dist[v] = dist[u] + 1 # otherwise a node can enter twice
q.append(v)
return order, distJavaScript
function bfs(adj, start) {
const seen = new Set([start]);
const dist = new Map([[start, 0]]);
const q = [start];
const order = [];
for (let head = 0; head < q.length; head++) { // index instead of shift()
const u = q[head];
order.push(u);
for (const v of adj.get(u) ?? []) {
if (!seen.has(v)) {
seen.add(v);
dist.set(v, dist.get(u) + 1);
q.push(v);
}
}
}
return { order, dist };
}Java
static Map<String,Integer> bfs(Map<String,List<String>> adj, String start) {
Map<String,Integer> dist = new HashMap<>();
Deque<String> q = new ArrayDeque<>();
dist.put(start, 0);
q.add(start);
while (!q.isEmpty()) {
String u = q.poll();
for (String v : adj.getOrDefault(u, List.of())) {
if (!dist.containsKey(v)) {
dist.put(v, dist.get(u) + 1);
q.add(v);
}
}
}
return dist;
}Worth noticing
It expands in rings
Every node at distance 1 is dequeued before any node at distance 2. Watch the distance labels: they never decrease along the queue. That property is the whole reason BFS finds shortest paths on unweighted graphs.
Mark on enqueue, never on dequeue
If you mark a node only when you dequeue it, a node with three unvisited neighbours can be enqueued three times before its first visit. The queue blows up and the complexity stops being O(V+E). This is the single most common BFS bug.
The queue holds at most two levels at once
So peak memory is the graph's maximum width, not its depth - the opposite trade-off from DFS. On a wide, shallow graph BFS can use far more memory than DFS.
Only shortest for unweighted edges
BFS assumes every edge costs the same. Add weights and the ring argument collapses - you need Dijkstra, which is BFS with a priority queue instead of a plain one.
Common pitfalls
- Marking nodes when dequeued instead of when enqueued. A node with three unvisited neighbours enters the queue three times and the run stops being O(V + E) - the single most common BFS bug.
- Using BFS on weighted graphs. It counts edges, not weight, so a 2-edge path of cost 100 beats a 3-edge path of cost 3. Weights need Dijkstra.
- Calling shift() on a JavaScript array as the queue. Each shift is O(n); walk a head index forward instead, as the implementation here does.
- Forgetting BFS covers only one connected component. Nodes unreachable from the start keep distance infinity - loop over unvisited nodes if you need the whole graph.
- Reconstructing paths without parent pointers. Store parent[v] = u at discovery time; walking those pointers backwards from the target is the path, for free.
Where it is used
- Degrees of separation in social graphs - LinkedIn's 2nd and 3rd connections are literally BFS rings.
- Shortest-move puzzles in interviews: word ladder, sliding puzzle, knight moves, rotten oranges - all BFS on an implicit graph.
- Web crawlers and network broadcast, which expand outward level by level from a seed.
- Garbage collectors and flood fill, marking everything reachable from a starting point.
Frequently asked questions
What is the time and space complexity of BFS?
O(V + E) time - each vertex is enqueued once and each edge examined once, twice in undirected graphs. Space is O(V): the seen set plus the queue, which holds at most two distance rings at a time, so peak memory tracks the graph's width.
BFS vs DFS - which one finds the shortest path?
BFS, and only on unweighted graphs. Its queue processes nodes in distance order, so the first arrival at any node is via a fewest-edges path. DFS dives down whatever branch comes first and can reach a node by a long detour.
Why must nodes be marked when enqueued rather than when dequeued?
Between discovery and processing a node sits in the queue; if it is not yet marked, every additional neighbour that sees it enqueues it again. Duplicates multiply, the queue can grow far past V entries, and the O(V + E) bound is gone.
Does BFS work on weighted graphs?
No. BFS minimises edge count, and with unequal weights the fewest-edge path need not be the cheapest. Dijkstra fixes exactly this by replacing the plain queue with a priority queue ordered by accumulated cost - the structure is otherwise the same.