1. One-Liner
BFS explores a graph layer by layer from a source, visiting all neighbors at distance k before any vertex at distance k+1.
2. The Problem It Solves
You need the shortest number of edges from a start vertex in an unweighted graph, to test connectivity, or to enumerate nodes in increasing distance order. BFS also underpins many graph primitives (connected components, bipartite checks with coloring).
3. The Core Idea
Think of ripples in a pond: the source drops a stone; the first ring is all vertices one edge away, the next ring two edges away, and so on. A FIFO queue enforces this “expand the frontier uniformly” behavior.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Mark source visited; enqueue it |
| 2 | While queue not empty: dequeue front vertex u |
| 3 | For each neighbor v of u: if unvisited, mark visited and enqueue v |
| 4 | Optionally record u in traversal order or parent pointers for path reconstruction |
| 5 | Stop when queue is empty — all reachable vertices processed |
5. Dry Run Example
Graph: 0—1—2 and 0—3 (undirected). Adjacency: 0→[1,3], 1→[0,2], 2→[1], 3→[0]. Start 0.
| Dequeue | Queue after | New visits | Order |
|---|---|---|---|
| — | [0] | — | — |
| 0 | [1,3] | 1, 3 | 0 |
| 1 | [3,2] | 2 | 0,1 |
| 3 | [2] | — | 0,1,3 |
| 2 | [] | — | 0,1,3,2 |
Shortest edge distances from 0: d(1)=d(3)=1, d(2)=2.
6. Key Properties
| Property | Detail |
|---|---|
| Unweighted shortest path | Yes — minimizes edge count |
| Weighted graphs | Does not replace Dijkstra for non-negative weights |
| Data structure | Queue (FIFO); level-order on trees |
| Completeness | Finds all reachable vertices in finite graphs |
7. Where It Is Used
| Company / System | Use |
|---|---|
| Google / Maps | Unweighted road subgraphs, social “degrees of separation” |
| Meta | Friend graph proximity, feed ranking layers |
| Network routing | RIP-style hop counts (conceptually), broadcast |
| Game AI | Grid shortest path (unweighted), flood fill |
| Compilers | Some data-flow on CFGs (with adaptations) |
8. Interview Tips
Interviewers expect: O(V+E) time/space clarity, why queue not stack, reconstruct path via parent array, and bidirectional BFS for single-pair shortest path in large graphs. Follow-ups: multi-source BFS, 0–1 BFS on 0/1 weights, BFS on implicit graphs.
9. Comparison with Other Algorithms
| Algorithm | Unweighted SP | Weighted SP | Space | Order |
|---|---|---|---|---|
| BFS | ✓ (edge count) | ✗ | O(V) | Level-order |
| DFS | Not shortest | ✗ | O(V) stack | Deep-first |
| Dijkstra | ✓ if weights 1 | ✓ non-neg | O(V)–O(E log V) | By distance |
| Bellman-Ford | — | ✓ with neg edges | O(V) | Relax rounds |
10. Complexity
| -- | -- |
|---|---|
| Time | O(V + E) — each vertex/edge touched once |
| Space | O(V) for queue + visited + parent (optional) |
| Best case | Still Ω(V + E) to confirm all edges in worst case |
Implementation Example (PYTHON)
from collections import deque
def bfs(adj, start):
n = len(adj)
vis = [False] * n
q = deque([start])
vis[start] = True
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
if not vis[v]:
vis[v] = True
q.append(v)
return order