Adjacency list

In an adjacency list in which the neighbors of each vertex are unsorted, testing for the existence of an edge may be performed in time proportional to the minimum degree of the two given vertices, by using a sequential search through the neighbors of this vertex.

If the neighbors are represented as a sorted array, binary search may be used instead, taking time proportional to the logarithm of the degree.

The main alternative to the adjacency list is the adjacency matrix, a matrix whose rows and columns are indexed by vertices and whose cells contain a Boolean value that indicates whether an edge is present between the vertices corresponding to the row and column of the cell.

In an adjacency matrix, this operation takes time proportional to the number of vertices in the graph, which may be significantly higher than the degree.

Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only |V|2/8 bytes of contiguous space, where |V| is the number of vertices of the graph.