next up previous contents index CD CD Algorithms
Next: War Story: Getting the Up: Graph Algorithms Previous: The Friendship Graph

Data Structures for Graphs


Selecting the right data structure to represent graphs can have an enormous impact on the performance of an algorithm. Your two basic choices are adjacency matrices and adjacency lists, illustrated in Figure gif.

An adjacency matrix is an tex2html_wrap_inline25067 matrix M where (typically) M[i,j] = 1 if there is an edge from vertex i to vertex j and M[i,j]=0 if there is not. Adjacency matrices are the simplest way to represent graphs. However, they doom you to using tex2html_wrap_inline25073 space no matter how many edges are in the graph. For large graphs, this will kill you. Remember that tex2html_wrap_inline25075 1,000,000, and work up from there. Although there is some potential for saving space by packing multiple bits per word or simulating a triangular matrix for undirected graphs, these cost some of the simplicity that makes adjacency matrices so appealing.  

Figure: The adjacency matrix and adjacency list of a given graph    

Beyond simplicity, there are certain algorithmic operations that prove faster on adjacency matrices than adjacency lists. In particular, it takes tex2html_wrap_inline25077 time to test whether edge (i,j) is in a graph represented by an adjacency matrix. All we must do is read the appropriate bit.

An adjacency list consists of an n-element array of pointers, where the ith element points to a linked list of the edges incident on vertex i. To test whether edge (i,j) is in the graph, we search the ith list for j. This takes tex2html_wrap_inline25083 , where tex2html_wrap_inline25085 is the degree of the ith vertex. For a complete or almost complete graph, tex2html_wrap_inline25087 , so testing the existence of an edge can be very expensive relative to adjacency matrices. However, tex2html_wrap_inline25089 can be much less than n when the graph is sparse. Most of the graphs that one encounters in real life tend to be sparse. Recall the friendship graph as an example. Further, a surprising number of the most efficient graph algorithms can be and have been designed to avoid such edge-existence queries. The key is processing the edges in a systematic order like breadth-first or depth-first search.  

For most applications, adjacency lists are the right way to go. The main drawback is the complexity of dealing with linked list structures. Things can be made arbitrarily hairy by adding extra pointers for special purposes. For example, the two versions of each edge in an undirected graph, (i,j) and (j,i), can be linked together by a pointer to facilitate deletions. Also, depending upon the operations you will perform on each list, you may or may not want it to be doubly linked, so that you can move backwards as easily as you move forwards.

It is a good idea to use a well-designed graph data type as a model for building your own, or even better as the foundation for your application. We recommend LEDA (see Section gif) as the best-designed general-purpose graph data structure currently available. It may be more powerful (and hence somewhat slower/larger) than what you need, but it does so many things right that you are likely to lose most of the potential do-it-yourself benefits through clumsiness.   

In summary, we have the following tradeoffs between adjacency lists and matrices:

Comparison Winner
Faster to test if (x, y) is in graph? adjacency matrices
Faster to find the degree of a vertex? adjacency lists
Less memory on small graphs? adjacency lists (m+n) vs. tex2html_wrap_inline25099
Less memory on big graphs? adjacency matrices (a small win)
Edge insertion or deletion? adjacency matrices O(1) vs. O(d)
Faster to traverse the graph? adjacency lists tex2html_wrap_inline25105 vs. tex2html_wrap_inline25107
Better for most problems? adjacency lists

next up previous contents index CD CD Algorithms
Next: War Story: Getting the Up: Graph Algorithms Previous: The Friendship Graph

Mon Jun 2 23:33:50 EDT 1997