What this module covers: Module A-4's DFS goes deep before it goes wide — following one path as far as it can before backtracking. BFS does the opposite: it explores layer by layer, using Module F-7's queue instead of Module F-6's stack. This module covers why that single structural swap gives BFS a property DFS can't offer — a guarantee of shortest path, measured in edge count, on an unweighted graph.
Layer by Layer, Using a Queue
BFS explores every neighbor of the starting node before moving on to their neighbors — exactly Module P-4's level-order traversal, generalized from a tree to a general graph, with the same visited-set addition Module A-4 introduced for handling cycles:
typescript
Compare the visited handling here directly to Module A-4's iterative DFS: DFS marked a node visited when it was popped (allowing the same node to sit in the stack multiple times simultaneously, discarded later when redundant), while BFS marks a node visited when it's enqueued — the moment it's first discovered, before it's even been processed. This isn't a stylistic choice; it's what guarantees BFS's core property, covered next.
Why BFS Guarantees Shortest Path (in Hops)
Because BFS processes nodes in strict FIFO order (Module F-7), and marks a node visited the instant it's first discovered, the first time any node is reached, it's guaranteed to have been reached via a shortest possible path from the start, measured in number of edges. Every node at distance 1 from the start gets enqueued before any node at distance 2 can be discovered (since distance-2 nodes are only reachable through a distance-1 node being processed first) — this is the exact same "every depth-d node is dequeued before any depth-(d+1) node" guarantee Module P-4 established for level-order tree traversal, now holding for a general graph.
typescript
DFS cannot offer this guarantee — it might stumble onto the target via a long, winding path long before it happens to try the short, direct one, since DFS commits to going deep along whichever neighbor it tries first, with no structural preference for "closer" nodes. This is the single most important reason to choose BFS over DFS: DFS answers "can I reach this node, and here's one way"; BFS answers "what's the fewest hops to reach this node."
Application: Shortest Path in a Grid
A grid is an implicit graph (Module A-4's numIslands, and Module A-9 in full) — BFS applied to a grid finds the minimum number of moves from a start cell to a target cell, moving one step at a time:
typescript
Same shape as shortestPathLength, with the graph's edges now generated implicitly (each cell's up/down/left/right neighbors) rather than read from an explicit adjacency list — the algorithm itself doesn't change at all, only how neighbors are computed. This is a recurring theme worth internalizing: a grid is just a graph whose edges are defined by a rule (adjacent cells) instead of an explicit list, and every graph algorithm in this course applies to it unchanged.
Where This Shows Up in Your Stack
"Degrees of separation" on a social network (previewed conceptually in Module P-6) is literally shortestPathLength run on the friendship graph — "how many hops from you to this other user" is exactly BFS's guaranteed-shortest-hop-count property, with no weighting involved.
Web crawlers exploring link structure breadth-first (crawl every page directly linked from the seed page before following links two hops away, and so on) use BFS specifically to prioritize discovering pages closer to the starting point first, which is often a reasonable proxy for relevance or importance in an unweighted link graph.
Network broadcast and routing protocols that need "minimum hop count to reach every other node" (some routing table construction algorithms, and network topology discovery tools) are running BFS from each node, for the same guaranteed-shortest-hops reason.
Word Ladder-style problems (transform one word into another, changing one letter at a time, each intermediate step a valid word) model words as nodes and single-letter transformations as edges — an implicit graph, exactly like the grid above — and BFS finds the minimum number of transformations, for the identical reason it finds minimum hops anywhere else.
Summary
BFS explores layer by layer using a queue (Module F-7), the direct graph generalization of Module P-4's level-order tree traversal — the mirror image of Module A-4's stack-based, depth-first DFS.
Marking a node visited at enqueue time, not dequeue time, is what guarantees the shortest-hop-count property — every node at distance d is fully enqueued before any node at distance d+1 can be discovered.
BFS guarantees shortest path in an unweighted graph, measured in edge count; DFS offers no such guarantee, since it commits to depth along whichever neighbor it tries first.
A grid is an implicit graph — the same BFS algorithm applies unchanged, with neighbors generated by a positional rule (adjacent cells) instead of read from an explicit adjacency list.
This is the mechanism behind "degrees of separation," breadth-first web crawling, and minimum-hop-count network routing — anywhere "fewest steps between two points, all steps equally costly" is the actual question being asked.
The next module, Shortest Paths I: Dijkstra's Algorithm, answers the question BFS can't: shortest path when edges have different costs — by replacing BFS's plain queue with Module A-1's min-heap.
Knowledge Check
Why does marking a node as visited at the moment it's enqueued (rather than when it's later dequeued) matter for BFS's correctness and its shortest-path guarantee?
Why can't DFS (Module A-4) guarantee finding the shortest path to a target node, while BFS can?
According to the module, why does shortestPathInGrid use the exact same algorithmic structure as shortestPathLength, despite grids and explicit adjacency-list graphs looking like very different kinds of input?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functionbfs(graph: Map<string,string[]>, start:string):string[]{const visited =newSet<string>([start]);// mark visited the moment it's ENQUEUED, not when dequeuedconst queue:string[]=[start];// Module F-7 — FIFOconst order:string[]=[];while(queue.length >0){const node = queue.shift()!;// a real Queue class (Module F-7) avoids this O(n) shift cost in production code order.push(node);for(const neighbor of graph.get(node)??[]){if(!visited.has(neighbor)){ visited.add(neighbor);// mark visited HERE, at enqueue time queue.push(neighbor);}}}return order;}
functionshortestPathLength(graph: Map<string,string[]>, start:string, target:string):number{if(start === target)return0;const visited =newSet<string>([start]);const queue:[string,number][]=[[start,0]];// [node, distance from start]while(queue.length >0){const[node, dist]= queue.shift()!;for(const neighbor of graph.get(node)??[]){if(neighbor === target)return dist +1;// first time reaching target — guaranteed shortestif(!visited.has(neighbor)){ visited.add(neighbor); queue.push([neighbor, dist +1]);}}}return-1;// target unreachable}