The Maze Exploration Analogy
Imagine you're exploring a maze with many branching paths. You have two strategies:
DFS (Depth-First Search)
Like a curious explorer who picks a path and follows it ALL THE WAY to the end. Hit a dead end? Backtrack to the last junction and try a different path.
Maze: Start → A → B → Dead End!
↓
Backtrack → A → C → Exit!
You go DEEP before going WIDE.
BFS (Breadth-First Search)
Like a cautious explorer who checks ALL ADJACENT ROOMS first, then moves one step further, checking all rooms at that distance.
Distance 0: Start
Distance 1: A, B, C (check all)
Distance 2: D, E, F (check all)
Distance 3: Exit found!
You go WIDE before going DEEP.
Visual Comparison
A
/|\
B C D
/| |\
E F G H
BFS Order (level by level):
A → B → C → D → E → F → G → H
DFS Order (deep before wide):
A → B → E → F → C → D → G → H
BFS explores in "waves" - all nodes at distance 1, then distance 2, etc.
DFS explores in "tunnels" - go as deep as possible, then backtrack.
How BFS Works
The Queue Approach
BFS uses a queue (first-in, first-out):
1. Add starting node to queue
2. Remove first node from queue, visit it
3. Add all its unvisited neighbors to queue
4. Repeat until queue is empty
Example on tree A-B-C-D-E-F-G-H:
Queue: [A] Visit: A, add B,C,D
Queue: [B,C,D] Visit: B, add E,F
Queue: [C,D,E,F] Visit: C
Queue: [D,E,F] Visit: D, add G,H
Queue: [E,F,G,H] Visit E, F, G, H
Queue: [] Done!
Order: A B C D E F G H (level by level)
Why BFS Finds Shortest Path
Since BFS visits nodes in order of distance from the start, the first time you reach a node is via a shortest path (for unweighted graphs).
Find shortest path from A to H:
BFS visits:
Distance 0: A
Distance 1: B, C, D ← D is H's parent!
Distance 2: H found!
Shortest path: A → D → H (2 steps)
How DFS Works
The Stack Approach (or Recursion)
DFS uses a stack (last-in, first-out) or recursion:
1. Start at root node
2. Visit current node
3. Pick an unvisited neighbor, go there (push to stack)
4. No unvisited neighbors? Backtrack (pop from stack)
5. Repeat until stack is empty
Example on tree A-B-C-D-E-F-G-H:
Stack: [A] Visit A, go to B
Stack: [A,B] Visit B, go to E
Stack: [A,B,E] Visit E, no children, backtrack
Stack: [A,B] Try F
Stack: [A,B,F] Visit F, no children, backtrack
Stack: [A,B] B done, backtrack
Stack: [A] Try C
...
Order: A B E F C D G H (deep before wide)
Why DFS Uses Less Memory (Sometimes)
DFS typically stores the current path, not all nodes at a level:
Wide tree (1000 children):
A
/||||||\
B C D ... Z (1000 nodes)
BFS: May need to hold many nodes in the queue
DFS: Typically holds the current path depth
Deep tree (1000 levels):
A - B - C - D - ... - Z (1000 deep)
BFS: Often holds just the frontier for each level in a long chain
DFS: May hold the entire path in the stack
Tree Traversals with DFS
For binary trees, DFS has three flavors based on when you visit the root:
1
/ \
2 3
/ \
4 5
Preorder (Root → Left → Right)
Visit root FIRST, then children.
Order: 1 → 2 → 4 → 5 → 3
Use: Copy a tree, prefix expressions
Inorder (Left → Root → Right)
Visit root BETWEEN children.
Order: 4 → 2 → 5 → 1 → 3
Use: Get sorted order from BST!
Postorder (Left → Right → Root)
Visit root LAST, after children.
Order: 4 → 5 → 2 → 3 → 1
Use: Delete a tree, postfix expressions
When to Use BFS vs DFS
| Use Case | Common Choice | Why |
|---|---|---|
| Shortest path (unweighted) | BFS | Finds shortest by design |
| Cycle detection | DFS | Track path with recursion stack |
| Topological sort | DFS | Postorder gives reverse order |
| Level-by-level processing | BFS | Natural level ordering |
| Path exists? | Either | Both work |
| All paths | DFS | Easier to track current path |
| Closest node matching condition | BFS | Finds nearest first |
| Deep tree, find any leaf | DFS | Uses less memory |
Quick Decision Rule
Need shortest path? → BFS
Need to explore all paths? → DFS
Need level order? → BFS
Working with recursion? → DFS
Space and Time Complexity
| Algorithm | Time | Space |
|---|---|---|
| BFS | O(V + E) | O(W) where W = max width |
| DFS | O(V + E) | O(H) where H = max height |
V = vertices (nodes), E = edges
Both visit every node once - same time complexity!
Space differs based on tree shape:
- Wide trees: DFS uses less space
- Deep trees: BFS uses less space
Common Pitfalls
1. Forgetting to Track Visited
Without tracking visited nodes, you'll loop forever in cyclic graphs!
2. Wrong Data Structure
BFS needs a queue (FIFO). DFS needs a stack (LIFO) or recursion. Mixing them gives wrong order.
3. Stack Overflow with DFS
Deep graphs + recursion = stack overflow. Use iterative DFS with explicit stack for very deep graphs.
4. BFS on Weighted Graphs
BFS finds shortest path by number of edges, not by weight. For weighted graphs, use Dijkstra's algorithm.
FAQ
Q: Which should I use by default?
DFS is often simpler (just recursion). Use BFS when you specifically need shortest path or level-order processing.
Q: Can I convert between BFS and DFS easily?
Yes! The main difference is queue (BFS) vs stack (DFS). Same overall structure.
Q: What if the graph is disconnected?
Run BFS/DFS from each unvisited node to cover all components.
Q: Why does BFS find a shortest path (in unweighted graphs)?
BFS explores in order of distance. The first time you reach a node, you've taken the minimum steps possible.
Summary
BFS and DFS are two fundamental ways to explore graphs and trees.
BFS (Breadth-First Search):
- Uses a queue
- Explores level by level
- Finds shortest path in unweighted graphs
- Better for: shortest path, level order
DFS (Depth-First Search):
- Uses a stack or recursion
- Explores as deep as possible first
- Three tree variations: preorder, inorder, postorder
- Better for: cycle detection, topological sort, path finding
Both are essential - know when to use each!
Related Concepts
Leave a Comment
Comments (0)
Be the first to comment on this concept.
Comments are approved automatically.