A state graph can easily be searched to find a goal state. In this example,
the goal state is one where all the pieces are positioned on peg C in the cor

rect order. By searching the state space it’s possible to not only find a
single solution, but to find every possible solution or the solution requiring
the fewest moves (or the most moves if that’s what you are looking for).
The average number of child nodes radiating from each parent node is
known as a graph’s branching factor. For some problems, such as the puz

zle example we have discussed here, the branching factor is low — on the
order of one to three branches per node — making it possible to represent
with a graph the entire state space in a computer’s memory. For many
domains though, the branching factor is much higher and the number of
potential states grows enormously as the distance from the root node (the
depth of the graph) increases. With these types of systems it’s impossible to
represent the entire state space because it will quickly exceed the memory
capabilities of even the most powerful computer. Even if such a graph
could be stored, it would still take eons to complete a search. Conse
quently, these types of graphs are created and searched by expanding a few
nodes at a time, typically (but not always) using algorithms that direct the
search toward the goal state.
Implementing a Graph Class
Two popular data structures used to represent graphs are adjacency matri
ces and adjacency lists. Adjacency matrix graphs use a twodimensional
matrix of Booleans or floats to store a graph’s connectivity information.
Booleans are used if there is no cost associated with traversing an edge and
floats are used when there is an associated cost, such as for a navigation
graph where each edge represents the distance between two nodes. The
exact implementation is, of course, up to the designer and the needs of his
problem. Figure 5.12 shows what the adjacency matrix looks like for the
digraph in Figure 5.6.
The Secret Life of Graphs  203
Implementing a Graph Class
Figure 5.12. An adjacency matrix