Breadth-First Search (BFS) in Python

Breadth-first search (BFS) is the algorithm you reach for when someone says "shortest path" in an unweighted graph. Drop a pebble in a pond — the ripple expands outward. BFS is that ripple, in code. 🌊

Why is it the go-to for shortest path? Because BFS visits nodes strictly in order of distance from the start: distance-1 neighbors first, then distance-2, then distance-3. The moment you bump into your target, you are guaranteed it took the fewest possible edges to get there.

How BFS Works

BFS is a level-by-level graph traversal python programmers use everywhere. You keep a queue of nodes to visit and a visited set. Pop the front, push unseen neighbors to the back, repeat until empty.

Let's walk a tiny graph:

    A
   / \
  B   C
 /   / \
D   E   F

Starting at A:

1. Queue: [A]. Pop A, enqueue B, C.

2. Queue: [B, C]. Pop B, enqueue D.

3. Queue: [C, D]. Pop C, enqueue E, F.

4. Pop D, E, F. Done.

Visit order: A → B → C → D → E → F. Every node at depth k is fully processed before any node at depth k+1 — that's the level guarantee.

Why a Queue (and not a stack)

Here's the elegant part: *the data structure is the algorithm*. Swap the queue for a stack and BFS becomes DFS — same code, completely different traversal.

BFS spreads, DFS plunges. The container picks the personality.

Implementation Notes

Always use collections.deque. It's not a stylistic preference — it's a complexity bug if you don't.

The deque python import you want is exactly:

from collections import deque
queue = deque([start])
queue.append(node)      # O(1) at the back
queue.popleft()         # O(1) at the front

The visited set. Mark a node visited the moment you enqueue it, not when you pop it. If you wait until popping, the same node can be enqueued many times by different neighbors before it's processed — duplicates explode and correctness suffers.

Tracking parents for path reconstruction. Carrying the full path inside the queue (like the snippet above) is readable but copies a list per enqueue. The scalable pattern is a parent dictionary: when you discover v from u, store parent[v] = u. After BFS, walk parents from target back to start and reverse the list.

Complexity Analysis

The representation matters too. With an adjacency list, finding a node's neighbors is O(text{deg}(v)), so the total scan is O(V + E). With an adjacency matrix, finding neighbors is always O(V) per node, pushing BFS to O(V^2) — fine for dense graphs, wasteful for sparse ones. Most real-world graphs (social, web, road networks) are sparse, so adjacency lists win.

BFS vs DFS

Common Pitfalls

1. Marking visited too late. Mark nodes visited at enqueue time, not dequeue. Otherwise you'll enqueue duplicates and blow up runtime.

2. Using a list as a queue. list.pop(0) is O(n). Always use deque.popleft().

3. Reconstructing paths wrong. Don't store the full path in every queue item if your graph is large — use a parent dict and reverse-walk at the end.

4. Assuming BFS works on weighted graphs. Shortest path unweighted only. The moment edges have weights ≠ 1, switch to Dijkstra or 0-1 BFS.

5. No `visited` set on cyclic graphs. Cycles will trap BFS in an infinite loop. The visited set is non-negotiable, even if you "know" the graph is a tree.

6. Forgetting directed vs undirected. In an undirected graph add both u→v and v→u. Forgetting the reverse edge silently breaks reachability.

Real-World Uses

BFS Variants

Frequently Asked Questions

Does BFS work on directed graphs? Yes. The algorithm is identical — only follow edges in their declared direction. Reachability becomes one-way, which is usually what you want.

Can BFS handle weighted graphs? Not for shortest path. BFS counts edges, not weights. Use Dijkstra for non-negative weights, Bellman-Ford for negative weights, or 0-1 BFS for the special 0/1 case.

Why is `deque.popleft()` $O(1)$? A deque is implemented as a doubly-linked list of fixed-size blocks. Removing from either end just adjusts a pointer — no element shifting, no reallocation.

How do I find the actual shortest path, not just the length? Maintain parent[child] = parent_node during BFS, then walk parents backward from target to start and reverse the list.

What's the difference between BFS and Dijkstra? BFS treats every edge as cost 1; Dijkstra uses a priority queue ordered by accumulated weight. On unweighted graphs they return the same answer, but BFS is faster and simpler. Add weights and you need Dijkstra.

Can BFS detect cycles? In undirected graphs, yes — if you reach an already-visited node that isn't your immediate parent, you've found a cycle. For directed graphs, DFS with recursion stack tracking is cleaner.

Master the queue, the visited set, and the parent map, and you've unlocked a huge chunk of graph problems. 🎉