BFS & DFS

Given a graph and a starting node, there are two fundamentally different orders in which you can visit every reachable node: breadth-first (spread outward one "ring" of distance at a time) and depth-first (commit to one path and follow it as far as possible before backtracking). Both are complete - both eventually visit every reachable node - but the order they visit nodes in, and the guarantees that order gives you, are very different.

Breadth-first search uses a queue (FIFO - first in, first out) to guarantee that every node at distance k from the start is visited before any node at distance k + 1. The start node is enqueued first; each time a node is dequeued, its unvisited neighbors are marked visited and enqueued. Because the queue preserves discovery order, and every neighbor of a distance-k node is at distance k or k+1, the traversal naturally exhausts one full "ring" of distance before touching the next.

Depth-first search instead commits to a neighbor immediately, recursing (or pushing onto an explicit stack) into that neighbor's subtree before ever returning to try a sibling neighbor. That "go all the way down one path before backing up" behavior is what recursion naturally gives you for free - each recursive call is itself a full depth-first exploration of everything reachable from that node.

Take the small undirected square graph from the previous chapter: A connects to B and C; B connects to A and D; C connects to A and D; D connects to B and C. Starting BFS from A: A is dequeued first and its neighbors B, C are enqueued; B is dequeued next and its only unvisited neighbor D is enqueued; C is dequeued (D is already visited, nothing new to enqueue); finally D is dequeued. The visit order is A, B, C, D - both of A's direct neighbors visited before D, which is two hops away. Starting DFS from A instead: visiting A recurses immediately into its first neighbor B; from B, the first unvisited neighbor is D, so DFS recurses into D immediately (skipping past C for now); from D, the only unvisited neighbor is C, so DFS visits C last. The visit order is A, B, D, C - notice C, one hop from the start, is visited *after* D, two hops away, because DFS commits to a path instead of expanding outward evenly.

• -BFS: queue-based, visits nodes in increasing order of distance from start, and is the standard way to find shortest paths in unweighted graphs.
• -DFS: recursion/stack-based, dives down one path fully before backtracking - useful for cycle detection, connectivity checks, and exploring all paths.
• -Both run in O(n + e) time and O(n) space, visiting every node and edge at most once - the difference is purely visit *order*, not asymptotic cost.