adjacencylist

An adjacency list is a data structure used to represent a graph by listing, for each vertex, the vertices to which it is connected. For every vertex v, the adjacency list contains the neighbors that v has an edge to, and, in weighted graphs, the corresponding edge weights. This representation is especially efficient for sparse graphs, where the number of edges E is much smaller than V squared.

In an unweighted graph, each adjacency list stores neighboring vertices. In a weighted graph, each entry typically stores a pair consisting of the neighbor and the edge weight. For directed graphs, the list for a vertex contains its outgoing edges; for undirected graphs, each edge is usually represented in both endpoints’ lists.

Space and time considerations: adjacency lists require O(V + E) space. Traversing all neighbors of a vertex v is O(deg(v)). Adding a vertex is typically O(1) amortized, and adding an edge is O(1) to append to the appropriate lists (assuming unsorted lists). Checking whether an edge exists between two vertices can be O(deg(v)) unless the neighbor lists are augmented with a hash set or map to enable faster lookups.

Variants and notes: adjacency lists can be implemented with arrays, linked lists, or hash maps. We can store weights by using a list of (neighbor, weight) pairs. Multi-graphs and self-loops are commonly supported by allowing multiple entries or self-edges. Compared to adjacency matrices, adjacency lists conserve space for sparse graphs but may incur slower edge-existence checks.

Use cases include graph traversal algorithms such as depth-first search and breadth-first search, as well as shortest-path algorithms like Dijkstra’s or Prim’s, where adjacency lists align well with iterative processing of neighbors. Language libraries often provide built-in adjacency list representations using maps or vectors.