Adjacency list
|
|
In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list.
If the graph is undirected, every entry is a set of two nodes containing the two ends of the corresponding edge; if it is directed, every entry is a tuple of two nodes, one denoting the source node and the other denoting the destination node of the corresponding arc.
As an example, the list {a,b},{a,c},{b,c} describes the undirected cyclic graph below, where all three nodes a,b,c are connected to each other.
Typically, adjacency lists are unordered.
In computer science, an adjacency list is a closely related data structure for representing graphs. In an adjacency list representation, we keep, for each vertex in the graph, all other vertices which it has an edge to (that vertex's "adjacency list"). For example, the graph pictured above has this adjacency list representation:
| a | adjacent to | b,c |
| b | adjacent to | a,c |
| c | adjacent to | a,b |
Trade-offs
The main competitor for 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 which are not present. Using a naive linked list implementation on a 32-bit computer, an adjacency list for an undirected graph requires about 16e bytes of storage, where e is the number of edges.
On the other hand, because each entry in the 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, 16e > n2/8, or the adjacency list representation occupies more space, precisely when d > 1/128. Thus a graph must be sparse indeed to justify an adjacency list representation.
Besides the space tradeoff, the different data structures also facilitate different operations. It's 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 know if two given vertices have an edge between them, this can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the vertices with the adjacency list.