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.