Adjacency list

From Wikipedia, the free encyclopedia

This undirected cyclic graph can be described by the list {a,b}, {a,c}, {b,c}.

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.

Typically, adjacency lists are unordered.

[edit] Application in computer science

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 instance, the representation suggested by van Rossum, in which a hash table is used to associate each vertex with an array of adjacent vertices, can be seen as an instance of this type of representation, as can the representation in Cormen et al in which an array indexed by vertex numbers points to a singly-linked list of the neighbors of each vertex.

One difficulty with the adjacency list structure is that it has no obvious place to store data associated with the edges of a graph, such as the lengths or costs of the edges. To remedy this, some algorithms texts such as that of Goodrich and Tamassia advocate a more object oriented variant of the adjacency list structure, sometimes called an incidence list, which stores for each vertex a list of objects representing the edges incident to that vertex. To complete the structure, each edge must point back to the two vertices forming its endpoints. The extra edge objects in this version of the adjacency list cause it to use more memory than the version in which adjacent vertices are listed directly, but are a convenient location to store additional information about each edge.

[edit] 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 which 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 n²/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 n² edges (allowing loops) we can let d = e/n² denote the density of the graph. Then, 8e > n²/8, or the adjacency list representation occupies more space, precisely when d > 1/64. Thus a graph must be sparse indeed for reduced space to justify an adjacency list representation. However, this analysis is valid only when the representation is intended to store only the connectivity structure of the graph, and not any numerical information about its edges.

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.

[edit] References

• Joe Celko (2004). Trees and Hierarchies in SQL for Smarties. Morgan Kaufmann, excerpt from Chapter 2: "Adjacency List Model". ISBN 1-55860-920-2. 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 527–529 of section 22.1: Representations of graphs. ISBN 0-262-03293-7. 
• David Eppstein (1996). ICS 161 Lecture Notes: Graph Algorithms.
• Michael T. Goodrich and Roberto Tamassia (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 0-471-38365-1. 
• Guido van Rossum (1998). Python Patterns — Implementing Graphs.