Step by Step
B
BFS — complete and optimal for unweighted graphs
Breadth-First Search explores level by level using a queue, guaranteeing it finds the shortest path (in terms of number of steps) for unweighted graphs.
Example: BFS exploring a maze level by level will find the shortest path in terms of number of moves, assuming every move costs the same.
D
DFS — memory efficient but not optimal
Depth-First Search explores as deep as possible along one path before backtracking, using a stack. It's memory efficient but doesn't guarantee the shortest or best path.
Example: DFS exploring a maze might find A path to the exit quickly, but not necessarily the shortest one.
U
Uniform Cost Search — optimal for weighted graphs
Expands the lowest-cost node first, guaranteeing optimality for graphs where edges have different costs (weighted graphs), unlike plain BFS which assumes equal cost per step.
Example: finding the cheapest route between cities where different roads have different toll costs, not just the fewest roads traveled.
A
A* — combines actual cost and heuristic estimate
Computes f(n) = g(n) + h(n), where g(n) is the actual cost from the start to the current node, and h(n) is a heuristic estimate of the remaining cost to the goal. A* is optimal specifically when the heuristic is admissible — meaning it never overestimates the true remaining cost.
Example: GPS navigation uses A* with straight-line distance as an admissible heuristic estimate of remaining distance to the destination.
Applied Walkthrough
1
A pathfinding algorithm for a video game needs to find the optimal route while also being reasonably fast, using an estimate of remaining distance to speed up the search.
2
Ask: which algorithm best combines actual cost so far with an estimate of remaining cost? A*, since it combines g(n) (actual cost) and h(n) (heuristic estimate).
3
For A* to guarantee finding the truly optimal path, the heuristic h(n) must be admissible — it must never overestimate the true remaining cost to the goal.
4
If the heuristic were allowed to overestimate, A* could potentially settle on a suboptimal path, since it would prematurely deprioritize a path that was actually better.
Exam Application
Exams test whether you can distinguish these four search algorithms by their guarantees (BFS: optimal for unweighted graphs; DFS: not optimal, memory efficient; Uniform Cost Search: optimal for weighted graphs; A*: optimal if heuristic is admissible) and whether you understand precisely what "admissible" means for a heuristic.
⚠ Common Trap
The most common trap is assuming any heuristic makes A* faster without checking whether it's admissible. A non-admissible heuristic (one that can overestimate the true cost) breaks A*'s optimality guarantee — A* might then return a path that looks good but isn't actually the truly optimal one.
✓ Quick Self-Check
1. What data structure does BFS use, and what guarantee does it provide for unweighted graphs?
A queue — it guarantees finding the shortest path in terms of number of steps for unweighted graphs.
Tap to reveal / hide
2. Is DFS guaranteed to find the optimal (shortest/cheapest) path?
No — DFS is memory efficient but does not guarantee optimality.
Tap to reveal / hide
3. What does Uniform Cost Search guarantee for weighted graphs?
It guarantees finding the optimal (lowest-cost) path, since it always expands the lowest-cost node first.
Tap to reveal / hide
4. What formula does A* use to decide which node to expand next?
f(n) = g(n) + h(n), where g(n) is actual cost from start and h(n) is the heuristic estimate to the goal.
Tap to reveal / hide
5. What condition must a heuristic satisfy for A* to guarantee optimality?
It must be admissible — it must never overestimate the true remaining cost to the goal.
Tap to reveal / hide