BFS, uniform-cost search, and A* can look nearly identical in code. Their difference is the priority assigned to the next frontier state.
Breadth-first search
BFS expands the shallowest state first. It is optimal when every action has the same cost because depth then equals path cost. A simple queue is sufficient.
Uniform-cost search
When action costs differ, prioritize the lowest accumulated cost g(n). A priority queue replaces the ordinary queue, and a state may need to be reconsidered if a cheaper route is discovered. With nonnegative costs, the first finalized goal has minimum cost.
A* search
A* prioritizes g(n)+h(n), combining cost so far with an estimate of remaining cost. An admissible heuristic never overestimates; a consistent heuristic also respects a triangle-like condition across each edge. Better heuristics can reduce expansions without changing the optimal result.
Continue with the book
Explore the full treatment, worked examples, and exercises in The AI Algorithms Compendium.
Adapted from The AI Algorithms Compendium, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.