|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
Consider the representation of a directed graph 
.
In addition to the 
GraphVertex class instances
and the 
GraphEdge class instances contained by the graph,
there is the storage required by the adjacency matrix.
In this case, the matrix is a 
matrix of Edges.
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 field.
Altogether there are linked lists elements
each of which refers to the linked list itself,
to the next element of the list
and contains 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 object references 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 30 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 © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.
