Consider the representation of a directed graph .
In addition to the `Vertex` class instances
and the `Edge` class instances contained by the graph,
there is the storage required by the adjacency matrix.
In this case, the matrix is a matrix
of pointers to `Edge` instances.
Therefore, the amount of storage required by an adjacency matrix
implementation is

On the other hand,
consider the amount of storage required
when we represent the same graph using adjacency lists.
In addition to the vertices and the edges themselves,
there are linked lists.
If we use the `LinkedList` class defined in Section ,
each such list has a `head` and `tail` pointer.
Altogether there are linked lists elements,
each of which consists of a pointer to the next element of the lists
and a pointer to an edge.
Therefore, the total space required is

Notice that the space for the vertices and edges themselves cancels out when we compare Equation with Equation . If we assume that all pointers require the same amount of space, we can conclude that adjacency lists use less space than adjacency matrices when

For example, given a 10 node graph, the adjacency lists version uses less space when there are fewer than 45 edges. As a rough rule of thumb, we can say that adjacency lists use less space when the average degree of a node, , satisfies .

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.