The Role of Data Structures in Traversal: A Comparative Memory Analysis of BFS and DFS

Graph traversal algorithms are a fundamental component of computational mathematics and computer science. The two most common methods, Breadth-First Search (BFS) and Depth-First Search (DFS), are often presented as distinct algorithms. This paper argues that BFS and DFS are, in fact, two variations of a single, generic traversal algorithm, and that their profound differences in behaviour including traversal order, optimality, and memory usage are a direct mathematical consequence of their underlying data structure: a Queue (First-In, First-Out) for BFS and a Stack (Last-In, First-Out) for DFS. We perform a theoretical space-complexity analysis, contrasting the exponential O( ) memory requirement of BFS with the linear-in-depth O(b.d) of DFS, where b is the branching factor and d is the depth. We then validate this theory with an empirical memory analysis on graph topologies specifically designed to target the worst-case scenarios for each algorithm. Our findings confirm that the choice of data structure is the defining factor that dictates the performance and feasibility of a graph traversal.