Breadth-First Search (BFS)

Intuition

Drop a stone in a still pond and watch the ripple spread: first it reaches everything one ring out, then everything two rings out, then three. Breadth-first search explores a graph exactly like that ripple. Starting from one node, it visits all the nodes one step away, then all the nodes two steps away, and so on — never going further until the closer ring is completely covered.

That "closest first" discipline is BFS's superpower. Because it reaches nodes in order of increasing distance, the first time BFS arrives at a node, it has arrived along a shortest path (counting edges). In an unweighted graph, BFS is the shortest-path algorithm.

To pull this off, BFS needs to remember the frontier — the nodes it has discovered but not yet explored from — in the exact order it found them. The right tool is a queue: first in, first out. New discoveries join the back; the next node to explore comes off the front. That single data-structure choice is the whole difference from depth-first search, which uses a stack (or recursion) and plunges deep instead of spreading wide.

How It Works

BFS is a short loop over a queue:

1. Put the start node in the queue and mark it visited, at distance 0.
2. While the queue is not empty:
3.   Dequeue the front node — this is the node we now explore.
4.   For each neighbour that is not yet visited: mark it visited, set its distance to current + 1, and enqueue it at the back.

The subtle, load-bearing detail is in step 4: mark a node visited the moment you enqueue it, not when you later dequeue it. If you wait until dequeue, the same node can be discovered by several neighbours and added to the queue multiple times — wasting work and corrupting the distances. Marking on enqueue guarantees each node enters the queue exactly once.

On a tree every node has exactly one path from the root, so the "not yet visited" check never rejects anything — there are no cross edges. On a general graph the check matters: it stops BFS from re-enqueueing a node it has already found. An edge pointing at an already-discovered node is a cross edge, and BFS simply skips it (the node already has its shortest distance from an earlier, equal-or-shorter path).

Each vertex is enqueued once and each edge examined once, giving O(V + E) time. The extra space is the queue plus the visited set, O(V).

Step By Step

The default configuration is a balanced binary tree of 7 nodes (0–6):

       0          level 0
      / \
     1   2        level 1
    / \ / \
   3  4 5  6      level 2

Adjacency list: 0 → [1, 2], 1 → [3, 4], 2 → [5, 6], and 3, 4, 5, 6 are leaves.

Watch the queue fill a whole level before draining it:

1. Enqueue 0 — mark 0 visited, d=0. Queue: [0].
2. Dequeue 0 — explore it. Neighbours 1 and 2 are unvisited → enqueue both, each at d=1. Queue: [1, 2].
3. Dequeue 1 — neighbours 3 and 4 unvisited → enqueue both at d=2. Queue: [2, 3, 4].
4. Dequeue 2 — neighbours 5 and 6 unvisited → enqueue both at d=2. Queue: [3, 4, 5, 6] — the entire bottom level now sits in the queue at once.
5. Dequeue 3, 4, 5, 6 in turn — each is a leaf with no unvisited neighbours, so the queue just drains. Queue empties.

Discovery (visit) order: 0, 1, 2, 3, 4, 5, 6

Distances: 0 is at d=0; 1, 2 at d=1; 3, 4, 5, 6 at d=2. Notice the contrast with depth-first search on the same tree: DFS would dive 0 → 1 → 3 before ever touching node 2, reaching order 0, 1, 3, 4, 2, 5, 6. BFS instead finishes the whole of level 1 (1, 2) before any level-2 node — and the queue, not a stack, is what enforces that.

Tree vs. Graph mode

• Tree mode (default): one path to each node, so BFS never meets an already-visited neighbour — no cross edges, no skips.
• Graph mode: edges may reconverge or form cycles. The visited set guards the queue; edges to already-discovered nodes are shown as cross edges and skipped. On the Simple preset, node 5 is reachable from both 2 and 4 — but 2 is dequeued first, so 2 → 5 is the tree edge (d(5) = 2) and 4 → 5 is the cross edge. (This is the exact flip from DFS, where 5 is reached via 4 first.) On the Cyclic preset, the cycle-closing edges like 2 → 0 and 5 → 1 all become cross edges, and the visited set is what makes the search terminate.

Complexity

• Time: each vertex is enqueued and dequeued once; each edge is examined once.
• Space: the queue and the visited set each hold at most O(V). The queue's peak is the widest "level" of the graph — for a broad, bushy graph that can be a large fraction of all vertices at once.

Edge Cases

• Single node, no edges: enqueue the start, dequeue it, find no neighbours, queue empties — done.
• Disconnected graph: BFS from one start only reaches its connected component; unreachable nodes are never enqueued and stay unvisited. To cover everything, restart BFS from each still-unvisited node.
• Cycles: the visited check turns every cycle-closing edge into a skipped cross edge, so the queue cannot grow forever.
• Wide vs. deep input: BFS's queue is biggest on wide graphs (a big frontier resident at once), exactly where DFS's stack stays shallow — the mirror image of DFS's deep-and-narrow cost.

Common Mistakes

1. Marking visited on dequeue instead of enqueue: lets a node get enqueued by several neighbours before it is ever processed — duplicated work and wrong distances. Mark it the instant it enters the queue.
2. Confusing BFS with DFS: BFS explores level by level with a queue (FIFO); DFS plunges deep with a stack or recursion (LIFO). Swapping the queue for a stack literally turns one into the other — the data structure is the difference.
3. Using BFS for shortest paths on a weighted graph: BFS counts edges, so it only finds shortest paths when every edge has the same cost. With varying weights you need Dijkstra's algorithm.
4. Forgetting the visited set on a graph: without it BFS loops forever around any cycle, re-enqueueing the same nodes endlessly.