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?