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.

Drop a stone in a pond and the ripples spread outward in rings: everything one ring away is reached before anything two rings away. That is breadth-first search. Now picture exploring a maze with a ball of string. You walk down one corridor as far as it goes, and only when you hit a dead end do you wind the string back to the last junction and try another turn. That is depth-first search.

• -A ring of the ripple is a level: all the nodes at the same distance from the start.
• -The order the ripples reach nodes is the queue: first discovered, first visited.
• -The ball of string is the call stack (or an explicit stack): it remembers the way back to the last junction.

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.

One practical catch: the recursive version uses one call-stack frame per level of depth, and Python allows about 1,000 by default. On a graph shaped like a long path of 2,000 nodes, dfs(graph, start) raises RecursionError. The fix is to make the stack explicit. Pushing neighbors in reversed order makes it visit them in the same order as the recursive version:

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, and D connects to B and C. First BFS from A:

• -Dequeue A. Its unvisited neighbors B and C are marked and enqueued.
• -Dequeue B. Its only unvisited neighbor is D, so D is enqueued.
• -Dequeue C. D is already visited, so nothing is enqueued.
• -Dequeue D. The queue is empty. Visit order: A, B, C, D.

Now DFS from A:

• -Visit A, and recurse at once into its first neighbor B.
• -From B, the first unvisited neighbor is D, so recurse into D immediately, leaving C for later.
• -From D, the only unvisited neighbor is C, so visit C last. Visit order: A, B, D, C.

Notice that C is one hop from A, yet DFS reaches it after D, which is two hops away, because DFS commits to a path instead of expanding evenly. BFS finishes both of A's neighbors before it goes any further. Step through both traversals in the demo below and watch how the queue and the stack differ.

• -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.