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.

Typically, adjacency lists are unordered.

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.

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 8"e" 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, 8"e" > "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.

References

* cite book
author = Joe Celko
title = Trees and Hierarchies in SQL for Smarties
pages = excerpt from Chapter 2: [http://www.SQLSummit.com/AdjacencyList.htm "Adjacency List Model"]
year = 2004
publisher = Morgan Kaufmann
id = ISBN 1-55860-920-2
* cite book
author = Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein
title = Introduction to Algorithms, Second Edition
publisher = MIT Press and McGraw-Hill
year = 2001
id = ISBN 0-262-03293-7
pages = 527–529 of section 22.1: Representations of graphs
* cite web
author = David Eppstein
year = 1996
title = ICS 161 Lecture Notes: Graph Algorithms
url = http://www.ics.uci.edu/~eppstein/161/960201.html
* cite book
author = Michael T. Goodrich and Roberto Tamassia
title = Algorithm Design: Foundations, Analysis, and Internet Examples
publisher = John Wiley & Sons
year = 2002
id = ISBN 0-471-38365-1
* cite web
author = Guido van Rossum
year = 1998
title = Python Patterns — Implementing Graphs
url = http://www.python.org/doc/essays/graphs/