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 .

An adjacency matrix is an 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 space no matter how many edges are in the graph. For large graphs, this will kill you. Remember that 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 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 , where is the degree of the ith vertex. For a complete or almost complete graph, , so testing the existence of an edge can be very expensive relative to adjacency matrices. However, 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 ) 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?

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?

Better for most problems? adjacency lists