219. What are the key differences between DFS and BFS?
MediumGraph algorithms
Technical
Show model answer
BFS explores in layers using a queue, so it finds shortest paths by edge count in unweighted graphs and produces a level structure. DFS goes deep using a stack (or recursion) and exposes structure: discovery and finish times, back edges for cycle detection, topological order, SCCs, bridges and articulation points.
Both run in O(V + E) with adjacency lists (O(V²) with a matrix). Memory differs: BFS stores the whole frontier, which can be O(V) and is large on wide graphs or trees (branching factor b to depth d gives O(b^d)); DFS stores the current path, O(depth), which is small on wide shallow graphs but can overflow the call stack on long paths, so iterative DFS is safer.