Start — ripples on a pond. Drop a pebble into still water and the ripple reaches everything one ring at a time: the nearest spots first, then the next ring out, then the next. Breadth-First Search explores a network exactly this way. Begin at one starting point, visit every immediate neighbor, then every neighbor-of-a-neighbor, and keep fanning outward ring by ring until everything reachable has been seen.
Build — a queue and the named pieces. A graph is just dots (called vertices, written $V$) joined by links (edges, $E$). BFS keeps the waiting vertices in a queue — a first-in, first-out line, like people at a ticket counter. Worked example: start at one person and add their 3 friends to the line; that whole first ring is “distance 1.” Process each of them and add their not-yet-seen friends as “distance 2,” and so on. Because you always finish a whole ring before opening the next, the first time you reach someone is along the fewest possible hops. That is exactly why BFS finds the shortest path in an unweighted graph.
Deepen — why the cost is $O(V+E)$. Mark a vertex as visited the moment you enqueue it (not when you later remove it), so it can never join the line twice. Then each vertex enters and leaves the queue exactly once → $O(V)$ work, and each edge is examined from both of its endpoints → $O(E)$ work. Added together, the running time is $O(V+E)$ — linear in the size of the graph. The memory needed is the width of the widest ring, at worst $O(V)$. The recorded parent of each vertex forms the BFS tree; following parent pointers backward from any vertex spells out a shortest route to the start. (Depth-First Search instead dives as deep as it can using a stack, and does not guarantee shortest paths.)
Try this in the panel above. The animated panel is a generic step-through demo of an algorithm trace. Use ▶│ Next to advance one operation at a time and ◀ Back to retrace it, so you can move at your own pace. Press Play, then drop the speed to 0.25× to watch each step settle before the next one fires. Finally, drag the n slider to a new size and press Reset to launch a fresh trace from the beginning.
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size (vertices V, edges E, or array length)
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average-case complexity
h
Height or depth of structure
k
Number of distinct values / items
Step 1 -- Layer-by-Layer Traversal. BFS explores all vertices at distance d from source before any vertex at distance d+1. Uses a FIFO queue. Visits vertices in order of their distance from source.
Step 2 -- Time Complexity. Each vertex is enqueued and dequeued at most once: O(V). Each edge is examined at most twice (once per endpoint): O(E). Total: O(V+E).
Step 3 -- Space Complexity. Queue holds at most one level of the BFS tree. Maximum queue size = width of widest level. Worst case (star graph): O(V). visited[] and dist[]: O(V). Total: O(V).
Step 4 -- Shortest Path in Unweighted Graph. dist[v] as computed by BFS is the minimum number of edges from source to v. Proof: BFS processes vertices in non-decreasing distance order. First time v is visited, its distance is minimal.
Step 5 -- BFS Tree. parent[] array defines a BFS tree. Path from source to v: follow parent pointers from v to source and reverse. All non-tree edges span same or adjacent levels (no back edges to distant ancestors, unlike DFS).
Step 6 -- Applications. Shortest path in unweighted graphs. Level-order tree traversal. Finding connected components. Bipartiteness check (2-coloring). Cycle detection in undirected graphs. Web crawlers. Social network friend distance (Six Degrees of Separation).
§4 — Frequently Asked Questions
Why does BFS give shortest paths in unweighted graphs? concept+
BFS processes vertices in non-decreasing distance order. When vertex v is first dequeued, it has been visited via the minimum-hop path. Any later path to v would be longer since it must go through unvisited vertices at equal or greater distance.
How is BFS different from DFS? concept+
BFS uses a queue (FIFO) -- explores all neighbors before going deeper. DFS uses a stack (LIFO) -- goes as deep as possible before backtracking. BFS gives shortest path in unweighted graphs. DFS does not. DFS uses O(h) space (height), BFS uses O(w) space (width).
2-color the graph during BFS: color source RED, color all neighbors BLUE, color their neighbors RED, etc. If any edge connects two vertices of the same color: not bipartite. If BFS completes without conflict: bipartite. O(V+E).
What is the BFS tree's structure? nonobv+
BFS tree has no cross edges between non-adjacent levels (cross edges always span 0 or 1 levels). This is because BFS processes level by level -- if an edge existed between level d and level d+2, the level-d+2 vertex would have been discovered earlier via its level-d+1 neighbor.
How does multi-source BFS work? deep+
Initialize queue with ALL sources at once (distance 0 for all). BFS then finds shortest distance from the nearest source to every vertex. Used for: nearest exit in a maze, nearest hospital from any location, 0-1 BFS on modified edge weights.
§5 — Common Misconceptions & Errors
Conceptual Misconceptions
✗ BFS finds shortest path in all graphs.
✓ BFS finds shortest PATH (fewest edges) only in UNWEIGHTED graphs. For weighted graphs, use Dijkstra (non-negative weights) or Bellman-Ford (negative weights allowed).
✗ BFS and DFS have the same space complexity.
✓ DFS: O(h) stack space where h = height. BFS: O(w) queue space where w = max level width. For balanced trees: both O(log n). For paths: DFS O(n), BFS O(1). For complete binary tree: DFS O(log n), BFS O(n/2).
✗ BFS always visits all vertices.
✓ BFS from a single source only visits vertices reachable from that source. For disconnected graphs, run BFS from each unvisited vertex to find all connected components.
Implementation Errors
✗ Forgetting to mark vertices as visited BEFORE enqueuing.
✓ If you mark after dequeuing, the same vertex can be enqueued multiple times (by different neighbors), causing O(V*E) runtime instead of O(V+E).
✗ Using a stack instead of a queue for BFS.
✓ A stack gives DFS behavior. Queue (FIFO) is essential for BFS level-by-level traversal. Using the wrong data structure silently gives wrong shortest paths.
✗ Not resetting visited[] between multiple BFS calls on the same graph.
✓ If visited[] is not cleared, subsequent BFS calls from different sources will skip already-visited vertices from previous runs.