adjacency-list representation

(data structure)

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.

Note: 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.

Authors: BB,PEB

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Fri Dec 17 12:27:37 2004.
HTML page formatted Mon Dec 19 14:07:45 2005.

Cite this as:
Bob Bockholt and Paul E. Black, "adjacency-list representation", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/adjacencyListRep.html