BFS vs DFS Differences (Traversal, Memory, Applications)

Detailed as in Q66/Q92 summary:

Traversal Order

• BFS: Level-order (queue) → visits neighbors layer by layer, yields vertices sorted by distance (edges) from source. Order: source, distance1, distance2...
• DFS: Depth-first (stack/recursion) → dives to deepest unvisited neighbor before backtracking, yields pre-order depth path.

Memory Usage

• BFS: Needs queue storing entire frontier; worst $O(V)$ but frontier can be wide → up to $O(b^d)$ for branching factor $b$, depth $d$; often more memory than DFS for wide graphs.
• DFS: Stack stores current path; $O(h)$ where $h$ = height/depth ($O(V)$ worst). Recursion stack $O(V)$ but typically smaller for deep narrow graphs. Risk of recursion overflow; iterative DFS also $O(V)$.
• Both $O(V)$ visited array + $O(V+E)$ or $O(V^2)$ graph storage.

Applications & Real-World

BFS:

• Unweighted shortest path (GPS with equal roads, social network degrees, web crawler breadth, peer-to-peer search).
• Bipartite testing, connected components, Edmonds-Karp max flow (BFS finds shortest augmenting path), broadcasting level synchrony.

DFS:

• Topological sort (DAG), cycle detection (back edge), strongly connected components (Kosaraju), articulation points/bridges, solving mazes/puzzles via backtracking, file system traversal.
• Memory-constrained search (when BFS frontier too large).

Tradeoff: Need shortest path on unweighted? BFS. Need any path / explore deep / detect cycles / topological? DFS. Need both? Use BFS for shortest, DFS for connectivity; iterative deepening combines benefits.