graph such as that for the Towers of Hanoi puzzle, then the best path
will be the one reaching the solution in the fewest steps.
Before I get to the nitty-gritty I’d like to make it clear that many of you are
initially going to find some of these algorithms difficult to understand. In
fact I think graph search algorithms should come with a health warning.
Something like the following would be appropriate:
Beware! Search algorithms have the ability to create in the average human
brain terrible amounts of frustration and confusion, leading to headaches,
nausea, and sleep deprivation. Spontaneous and excessive howling is not
uncommon. Please be aware these symptoms are commonplace in the early
stages of the learning curve and are not generally cause for concern. Nor
mal service is usually resumed within a reasonable length of time. (If
symptoms persist, however, stay clear of busy roads, razor blades, and
loaded weapons. Seek medical advice at the earliest opportunity.)
Seriously though, for many people this stuff can be difficult to understand.
For this reason I’m going to take my time explaining each algorithm. It’s
very important that you understand the theory and don’t just use these tech-
niques in a “cut and paste” fashion, because often you may want to modify
an algorithm to suit your own requirements. Without an understanding of
how these searches work, any modification will be almost impossible and
you’ll be left scratching your head in frustration.
Strap yourself into your seat then. Let’s get on with it!
Uninformed Graph Searches
Uninformed graph searches, or blind searches as they are sometimes
known, search a graph without regard to any associated edge costs. They
can distinguish individual nodes and edges however, enabling them to
identify a target node or to recognize previously visited nodes or edges.
This is the only information required to either completely explore a graph
(to visit every node) or find a path between two nodes.
Depth First Search
Meet little Billy. Billy is standing at the entrance to a typical theme park: a
conglomeration of rides and other attractions and the paths meandering
through the park that connect them. Billy doesn’t have a map but he’s eager
to discover what rides and other entertainment the park has to offer.
Fortunately Billy knows about graph theory and he quickly spots the
similarity between the layout of a theme park and a graph. He sees that
each attraction can be represented by a node and the paths between them
by edges. Knowing this, Billy can ensure he visits every attraction and
walks down every path using a search algorithm called the depth first
search, or DFS for short.
210 | Chapter 5
Graph Search Algorithms