Breadth First Search (BFS): Level-Order Graph Traversal
Learn Breadth First Search (BFS) on graphs — the queue-and-visited-set pattern, a worked walkthrough, JavaScript code, and time and space complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Breadth First Search is the traversal you reach for when distance matters. It explores a graph in rings: first the start node, then everything one hop away, then everything two hops away, and so on. That expanding-wave order is exactly why BFS finds the shortest path in an unweighted graph — the first time you reach a node, you've reached it by the fewest possible edges.
The mechanism behind that guarantee is almost embarrassingly small: a queue to hold nodes waiting to be explored, and a visited set so you never process the same node twice. Get those two pieces right and the level-order behavior falls out for free.
Learn the plain traversal here and you've got the skeleton for a dozen harder problems — shortest path in a grid, cloning a graph, counting connected components, and word-ladder puzzles all wear this exact loop underneath.
The problem
You're given a graph as an adjacency list: an array where index i holds the list of nodes directly connected to node i. Starting from node 0, visit every reachable node and return the order in which you visited them.
Input: adjList = [[1, 2], [0, 3], [0, 3], [1, 2]]
// node 0 -> {1, 2}
// node 1 -> {0, 3}
// node 2 -> {0, 3}
// node 3 -> {1, 2}
Output: [0, 1, 2, 3]This graph is a square: 0 sits at one corner, 1 and 2 are its neighbors (distance 1), and 3 is the opposite corner (distance 2). BFS visits 0, then the whole distance-1 ring {1, 2}, then the distance-2 ring {3} — never jumping ahead to a far node before finishing a closer one.
The brute force baseline
Suppose you ignored the level-order discipline and just tried to "reach everything" by repeatedly scanning for any node connected to something you've already seen. Without a queue, you'd re-scan the entire graph on every pass to find the next frontier:
function reachAll(adjList) {
const visited = new Set([0]);
let changed = true;
while (changed) {
changed = false;
for (let node = 0; node < adjList.length; node++) {
if (!visited.has(node)) continue;
for (const nbr of adjList[node]) {
if (!visited.has(nbr)) {
visited.add(nbr);
changed = true; // grew the frontier, must sweep again
}
}
}
}
return [...visited];
}This gets the right set of nodes, but it re-sweeps the full adjacency list once per "layer" it discovers, and it gives you no clean notion of visitation order or distance. On a long chain of n nodes it degrades toward O(n²) work because each outer sweep advances the frontier by only one node. The fix isn't a smarter scan — it's remembering which nodes to explore next, in order.
The key insight: a FIFO queue enforces level order
The moment you discover a node, you don't have to act on it immediately — you just need to remember to come back to it, and to come back to nodes in the same order you found them. That's a queue: first in, first out.
Here's why FIFO produces level order. When you dequeue the start node and enqueue its neighbors, every distance-1 node lands in the queue before any distance-2 node exists. Because the queue hands nodes back in arrival order, you fully drain the distance-1 ring before the first distance-2 node ever comes up. Induction does the rest: distance-d nodes always leave the queue before distance-d+1 nodes enter it.
Two rules keep it correct and fast:
- Mark visited at enqueue time, not at dequeue time. If you wait until dequeue, the same node can be pushed multiple times by different neighbors before it's ever processed.
- Check
visitedbefore enqueueing. This is what stops cycles from looping forever — in the square above, node3is a neighbor of both1and2, but only the first discovery enqueues it.
The optimal solution
This is the exact algorithm the visualizer animates: a queue, a visited set, and a result list built up in traversal order.
function bfs(adjList) {
const visited = new Set();
const queue = [];
const result = [];
const startNode = 0;
visited.add(startNode); // mark BEFORE enqueue
queue.push(startNode);
while (queue.length > 0) {
const curr = queue.shift(); // FIFO: take the oldest node
result.push(curr);
for (const neighbor of adjList[curr] || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor); // mark on discovery
queue.push(neighbor);
}
}
}
return result;
}The visited.add(startNode) before the loop is the base case; the if (!visited.has(neighbor)) guard inside is what makes the whole thing terminate on cyclic graphs. Everything else is just draining the queue.
One production note: queue.shift() on a JavaScript array is O(n) because it re-indexes the whole array. For large graphs, track a head pointer (let head = 0; const curr = queue[head++];) or use a real deque so each dequeue stays O(1). It doesn't change the Big-O story below, but it changes whether your solution times out.
Walkthrough
Tracing adjList = [[1, 2], [0, 3], [0, 3], [1, 2]] from node 0. Watch the queue drain one ring at a time.
| Step | curr | Neighbors checked | queue (front → back) | visited | result |
|---|---|---|---|---|---|
| init | — | — | [0] | {0} | [] |
| 1 | 0 | 1 → new, 2 → new | [1, 2] | {0,1,2} | [0] |
| 2 | 1 | 0 → seen, 3 → new | [2, 3] | {0,1,2,3} | [0,1] |
| 3 | 2 | 0 → seen, 3 → seen | [3] | {0,1,2,3} | [0,1,2] |
| 4 | 3 | 1 → seen, 2 → seen | [] | {0,1,2,3} | [0,1,2,3] |
Step 3 is the payoff. When we process node 2, its neighbor 3 is already in visited — it was discovered back in step 2 while processing node 1. The visited check skips it, so 3 is enqueued exactly once and the traversal can't loop. The queue empties at step 4, and result = [0, 1, 2, 3] is the level order: the source, then its ring, then the far corner.
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(V + E) | Each vertex is enqueued/dequeued once (V), and each edge is examined once when its owner is processed (E). |
| Space | O(V) | The visited set and the queue each hold at most V nodes; the queue peaks at one full frontier. |
V is the number of vertices, E the number of edges. You touch every node once and every edge once — there's no repeated work, which is the whole point of the visited set. (The naive re-sweep baseline was O(V²) precisely because it lacked one.) With the array shift() caveat handled by a head pointer, this O(V + E) bound is tight.
Common mistakes
- Marking visited at dequeue instead of enqueue. A node with several parents gets pushed multiple times, inflating the queue and re-processing nodes. Mark it the instant you discover it.
- Using a stack (LIFO) by accident.
push+popgives you Depth First Search, not BFS. You needpush+shift(or a head pointer) so the oldest node leaves first. - Forgetting the visited check enables cycles. Any graph with a cycle — even a simple triangle — loops forever without the
if (!visited.has(neighbor))guard. - Assuming BFS finds shortest paths in weighted graphs. BFS counts edges, not weights. The moment edges have different costs, you need Dijkstra, not BFS.
queue.shift()on huge inputs. It's O(n) per call in JavaScript, quietly turning your O(V + E) solution into O(V²). Use a head index for large graphs.
Where this pattern shows up next
The queue-and-visited-set loop is the backbone of most graph problems. Once it's automatic, these build directly on it:
- Clone Graph — the same BFS, but you build a mirror node for each one you dequeue.
- Max Area of Island — flood-fill a grid, where each cell's four sides are its "edges."
- Find if Path Exists in Graph — stop the traversal early the moment you dequeue the destination.
- All Paths From Source to Target — the DFS counterpart, where you carry the path itself instead of a visited set.
You can also step through BFS interactively and watch the frontier rings expand distance by distance, one dequeue at a time.
FAQ
What is the difference between BFS and DFS?
BFS explores a graph level by level using a queue (FIFO), fanning out to all distance-1 nodes before any distance-2 node. DFS dives as deep as possible down one branch before backtracking, using a stack (or recursion). The practical consequence: BFS finds the shortest path in an unweighted graph because it reaches each node by the fewest edges, while DFS is better suited to problems about full paths, cycle detection, and topological ordering.
Why does BFS use a queue instead of a stack?
The queue's first-in-first-out order is what produces level-order traversal. Because neighbors are enqueued in the order they're discovered, every node at distance d leaves the queue before any node at distance d+1 enters processing. Swap the queue for a stack and you get last-in-first-out behavior, which dives deep into one branch first — that's Depth First Search, and it loses the shortest-path guarantee.
What is the time complexity of BFS?
O(V + E), where V is the number of vertices and E the number of edges. Each vertex is enqueued and dequeued exactly once, and each edge is inspected once when its source node is processed. Space is O(V) for the visited set plus the queue, which at its peak holds a single full frontier of nodes. One caveat in JavaScript: array.shift() is O(n), so use a head pointer or a deque on large graphs to keep dequeues O(1).
Why do we mark nodes as visited when enqueueing rather than dequeueing?
Marking at enqueue time prevents the same node from being pushed onto the queue multiple times. If node 3 is a neighbor of both node 1 and node 2, and you only mark visited on dequeue, both would enqueue it before either dequeues it — wasting work and bloating the queue. Marking on discovery guarantees each node enters the queue exactly once, which is what keeps the total work at O(V + E) and prevents infinite loops on cyclic graphs.
Does BFS work on graphs with cycles?
Yes, and the visited set is precisely what makes it safe. Before enqueueing any neighbor, BFS checks whether it has already been seen; a node reachable through a cycle is skipped on every discovery after the first. Without that check, a cycle like a triangle would loop forever, endlessly re-enqueueing nodes. With it, every reachable node is processed once regardless of how many cycles the graph contains.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.