Adjacency list

Adjacency lists are a popular way to represent graphs in algorithmic design. Each node $x$ in the graph is assigned an adjacency list that consists of nodes to which there is an edge from $x$.

Adjacency lists for directed graphs can be stored as an array of vectors: vector<int> adj[N], where N is a constant denoting the number of nodes in the graph.

vector<int> adj[N];
adj[1].push_back(2);
// etc.

For an undirected graph, each edge is added in both directions. For a weighted graph, we can extend the structure with the following, where the second int in the pair $(b,w)$ is the weight associated with the edge from node $a$ to $b$.

vector<pair<int, int>> adj[N];

Implications

The benefit of using adjacency lists is that we can efficiently find the nodes to which we can move from a given node through an edge. For example, we can use a simple iterator-based loop through a node $x$‘s adjacency list.

List representations are ideal if $|E|$ is much less than $|V{|}^2$, i.e., if the graph is sparse.

See also

• Adjacency matrix