6
breadth-first
search
This chapter introduces graphs. First, I’ll talk about what graphs
are (they don’t involve an X or Y axis). Then I’ll show you your first
graph algorithm. It’s called
breadth-first search
(BFS).
Breadth-first search allows you to find the shortest distance
between two things. But shortest distance can mean a lot of things!
You can use breadth-first search to
• Write a checkers AI that calculates the fewest moves to victory
96
Chapter 6
I
Breadth-first search
• Write a spell checker (fewest edits from your misspelling to a real
word—for example, READED -> READER is one edit)
• Find the doctor closest to you in your network
Graph algorithms are some of the most useful algorithms I know. Make
sure you read the next few chapters carefully—these are algorithms
you’ll be able to apply again and again.
Introduction to graphs
Suppose you’re in San Francisco, and you want to go from Twin Peaks
to the Golden Gate Bridge. You want to get there by bus, with the
minimum number of transfers. Here are your options.
97
Introduction to graphs
What’s your algorithm to find the path with the fewest steps?
Well, can you get there in one step? Here are all the places you can get
to in one step.
The bridge isn’t highlighted; you can’t get there in one step. Can you get
there in two steps?
Again, the bridge isn’t there, so you can’t get to the bridge in two steps.
What about three steps?
|
