- 2072 Magh · 5 marks
Differences between DFS and BFS
Short answer
DFS uses a stack (or recursion), going deep before backtracking; BFS uses a queue, visiting level by level. DFS memory is O(depth), BFS O(width). BFS finds shortest paths in unweighted graphs; DFS does not guarantee that.
What are the differences between DFS and BFS?
| Point | DFS (depth first) | BFS (breadth first) |
|---|---|---|
| Data structure | Stack (or recursion) | Queue |
| Order | Goes deep along a path, then backtracks | Visits level by level |
| Memory | O(depth) of the path in a tree | O(width), can be large (all vertices of a level) |
| Shortest path | Does not guarantee it | Finds shortest path in an unweighted graph |
| Time | O(V + E) with lists | O(V + E) with lists |
| Applications | Cycle detection, topological sort, connected components, maze solving | Shortest path, level-order, nearest neighbours, web crawling |
| Completeness | May go very deep (infinite path problem) | Finds a solution at the shallowest level |
| Implementation | Simple with recursion | Needs explicit queue |
Example: for the tree A-(B, C), B-(D, E), BFS gives A B C D E, DFS gives A B D E C.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- BFS and DFS with example · Data Structure and Algorithm, chapter 10 · asked 4×
- Searching: BFS vs DFS comparison · Artificial Intelligence, chapter 3 · asked 5×
- Informed vs blind search; DFS vs BFS · Artificial Intelligence, chapter 3
- DFS; stateless vs stateful services · Distributed System, chapter 2