Two popular data structures used to represent graphs are adjacency matrices and adjacency lists. Adjacency matrix graphs use a two-dimensional 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.
Figure 5.12: An adjacency matrix
Each "1" represents a connection between two nodes, and each "0" represents 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 unnecessary 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 example.
Figure 5.13: An adjacency list representation of the digraph from Figure 5.6
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 to N + E (number of nodes + number of edges), whereas for an adjacency matrix it is proportional to N2 (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.