Each “1” represents a connection between two nodes, and each “0” repre
sents the lack of a connection. By reading the values directly off the matrix
from Figure 5.12, we know that there is no connection from node 2 to 6,
but there is an edge connecting 4 to 2.
Adjacency matrices are intuitive, but for large sparse graphs this type of
representation is inefficient as most of the matrix is used storing unneces
sary zero values. A much better data structure for sparse graphs (the most
commonly occurring graphs in game AI) is the adjacency list.
For each node present, an adjacency list graph stores a linked list of all
its adjacent edges. Figure 5.13 shows how this works for the previous
Adjacency lists are efficient for storing sparse graphs because they don’t
waste space storing null connections. The amount of space required to store
a graph using this type of data structure is proportional toN+E(number
of nodes + number of edges), whereas for an adjacency matrix it is propor
tional to N
(number of nodes squared).
As most of the graphs you will come across in AI game development are
sparse, an adjacency list will frequently be your data structure of choice.
With this in mind let’s take a look at the source code required to implement
such a graph.
The GraphNode Class
GraphNode encapsulates the minimum information a node requires for an
adjacency list graph representation: a unique identifying number, or index.
Here’s the listing of the graph node declaration:
//every node has an index. A valid index is >= 0
204 | Chapter 5
Implementing a Graph Class
Figure 5.13. An adjacency list representation of the digraph from Figure 5.6