Trade-offs
The main alternative to the adjacency list is the adjacency matrix. For a graph with a sparse adjacency matrix an adjacency list representation of the graph occupies less space, because it does not use any space to represent edges that are not present. Using a naive array implementation of adjacency lists on a 32-bit computer, an adjacency list for an undirected graph requires about 8e bytes of storage, where e is the number of edges: each edge gives rise to entries in the two adjacency lists and uses four bytes in each.
On the other hand, because each entry in an adjacency matrix requires only one bit, they can be represented in a very compact way, occupying only n2/8 bytes of contiguous space, where n is the number of vertices. Besides just avoiding wasted space, this compactness encourages locality of reference.
Noting that a graph can have at most n2 edges (allowing loops) we can let d = e/n2 denote the density of the graph. Then, if 8e > n2/8, the adjacency list representation occupies more space, which is true when d > 1/64. Thus a graph must be sparse for an adjacency list representation to be more memory efficient than an adjacency matrix. However, this analysis is valid only when the representation is intended to store the connectivity structure of the graph without any numerical information about its edges.
Besides the space trade-off, the different data structures also facilitate different operations. It is easy to find all vertices adjacent to a given vertex in an adjacency list representation; you simply read its adjacency list. With an adjacency matrix you must instead scan over an entire row, taking O(n) time. If you, instead, want to perform a neighbor test on two vertices (i.e., determine if they have an edge between them), an adjacency matrix provides this at once. However, this neighbor test in an adjacency list requires time proportional to the number of edges associated with the two vertices.
Read more about this topic: Adjacency List
Famous quotes containing the word trade-offs:
“Realistic about how much one person can accomplish in a given day, women expect to have to make some trade-offs between work and family. Families, however, have absorbed all the stress and strain they possibly can. The entire responsibility for accommodation is taking place on the home side of the equation.”
—Deborah J. Swiss (20th century)
“Work-family conflicts—the trade-offs of your money or your life, your job or your child—would not be forced upon women with such sanguine disregard if men experienced the same career stalls caused by the-buck-stops-here responsibility for children.”
—Letty Cottin Pogrebin (20th century)