Definition: A representation of a directed graph with n vertices using an array of n lists of vertices. List i contains vertex j if there is an edge from vertex i to vertex j. A weighted graph may be represented with a list of vertex/weight pairs. An undirected graph may be represented by having vertex j in the list for vertex i and vertex i in the list for vertex j.
See also adjacency-matrix representation, sparse graph.
Suppose we have a directed graph with four vertices. Here are adjacency-matrix and adjacency-list representations. The arrow (->) means a link in a list.
1 2 3 4
1 1 1 1 1
2 1 0 0 0
3 0 1 0 1
4 0 1 1 0
1 -> 1 -> 2 -> 3 -> 4
2 -> 1
3 -> 2 -> 4
4 -> 2 -> 3
One variant is to have an array of columns, rather than rows, with the list going "down". The adjacency-list representation is more compact for a sparse matrix.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 August 2008.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Bob Bockholt and Paul E. Black, "adjacency-list representation", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/adjacencyListRep.html