Graph Traversal Strategies¶

The frontier data structure (queue vs. stack) determines traversal order; BFS explores by distance layers while DFS explores depth-first, each revealing different graph properties.

Tension Addressed¶

Time vs. Space (BFS requires O(width) space, DFS requires O(depth) space)

Recognizable As¶

Any exploration of connected structure; queue-based yields shortest paths in unweighted graphs; stack-based yields cycle detection and topological ordering.

Canonical Sources¶

Moore, "Shortest Path Through a Maze," 1959; Tarjan, "Depth-First Search and Linear Graph Algorithms," 1972

Transfers To¶

Web crawlers, file system traversal, social network analysis, garbage collection, dependency resolution

BFS and DFS are not just algorithms but exploration paradigms. The choice encodes what "progress" means: BFS guarantees finding closest matches first; DFS minimizes memory in deep structures.