5GRAPHS AND BREADTH-FIRST SEARCH
In this chapter, we’ll study three problems in which we’re asked to solve puzzles 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? Breadth-first search (BFS) is the unifying algorithm here. BFS dispatches these problems, and it applies more generally whenever we want to solve a puzzle with 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, 2nd Edition 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.
