Adjacency List

graph-theory data-structures

Definition

Adjacency List

An adjacency list is a data structure used to represent a graph as a collection of unordered lists. Formally, for each vertex , the adjacency list contains all vertices such that there exists an edge .

Computational Properties

Space Complexity: Requires space, making it highly efficient for sparse graphs.

Lookup Efficiency: Finding all neighbours of a vertex takes time, while checking the existence of a specific edge also requires time.

Comparison: Unlike the adjacency matrix, the adjacency list does not require storage, though edge lookups are generally slower for dense graphs.