4GRAPHS AND BREADTH-FIRST SEARCH
In this chapter, we’ll study three problems in which we’re asked to solve a puzzle in the minimum number of moves. How quickly can a knight catch a pawn? How quickly can a student climb a rope in gym class? How cheaply can we translate a book written in one language to other target languages? The unifying algorithm here is breadth-first search (BFS). BFS dispatches these problems, and it applies more generally whenever we want to solve a puzzle in the minimum number of moves. Along the way, we’ll learn about graphs, a powerful way to model and solve problems that involve objects and connections between those objects. ...
Get Algorithmic Thinking now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
