Adjacency list

An adjacency list keeps, for every vertex of a graph, the list of its neighbours. Most graph algorithms take a vertex and go over its neighbours, and the adjacency list gives them in time proportional to their number.

It is the usual way to store a graph read from the input. Take an adjacency matrix instead when the graph has at most about 5000 vertices and the program mostly asks whether there is an edge between two given vertices.

How it works

A graph has 8 vertices, and the input gives its 9 edges one per line, as pairs of vertices: 1 2, 1 3, 2 4, 3 4, 2 5, 4 6, 3 6, 6 7, 4 5.

A graph with 8 vertices and 9 edges beside a table whose row v holds the adjacency list of vertex v: 1: 2 3; 2: 1 4 5; 3: 1 4 6; 4: 2 3 6 5; 5: 2 4; 6: 4 3 7; 7: 6; row 8 is empty and row 0 is grey. Vertex 4, its four edges and its list are blue.

Fig. 1. Row $v$ holds the list of vertex $v$ , one neighbour per cell; row 0 is not used. The list of 4 follows the order of the input lines that mention 4: 2 4, 3 4, 4 6, 4 5. Vertex 8 has no neighbours.

The number of neighbours of a vertex $v$ is its degree, written $de g v$ : the length of its list. Vertex 4 has degree 4, and vertex 8 has degree 0.

Before any edge is read, every vertex gets an empty list, including vertex 8, which no line mentions. Then each line makes its two ends neighbours of each other: 4 6 writes 6 at the end of the list of 4, and 4 at the end of the list of 6.

The adjacency lists of the 8-vertex graph filled one input line at a time, step 1.

Every vertex starts with an empty list, vertex 8 too.

1/10

Fig. 2. Each line read adds one number to each of two lists (blue).

After the nine lines the lists are the ones in Fig. 1. Each line adds two numbers, so the lists hold 18 numbers in all, two for every edge.

To check whether there is an edge between $u$ and $v$ , look for $v$ in the list of $u$ : there is no 7 in the list of 4, so 4 and 7 are not joined.

With $n$ vertices and $m$ edges, the costs in big-O notation are:

Operation	Cost
Create $n$ empty lists	$O (n)$
Add an edge	$O (1)$ on average
Go over the neighbours of $v$	$O (de g v)$ O(\deg v)
Degree of $v$	$O (1)$
Is there an edge between $u$ and $v$ ?	$O (de g u)$ O(\deg u)
Memory	$O (n + m)$ O(n + m)

In C++

The vertices are numbered from 1 to n, and the lists are a vector of vectors:

vector<vector<int>> adj(n + 1);

This creates n + 1 empty lists, so adj[v] is the list of vertex v, and adj[0] stays unused. adj[u].push_back(v) adds v to the list of u, for (int u : adj[v]) goes over the neighbours of v, and adj[v].size() is the degree of v.

The program reads n and m, then m lines u v, builds the lists of an undirected graph and prints them; the marked line is the one to remove for a directed graph. For the example the input is:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    // create the lists
    vector<vector<int>> adj(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        // add the edge to both lists
        adj[u].push_back(v);
        adj[v].push_back(u);   // remove this line if the graph is directed
    }

    for (int v = 1; v <= n; v++) {
        cout << v << ":";
        // go over the neighbours of v
        for (int u : adj[v]) {
            cout << ' ' << u;
        }
        cout << '\n';
    }
}

Building the lists and going over all of them both take $O (n + m)$ O(n + m) time.

Directed graphs

In a directed graph, the line u v is an edge from u to v, so it goes only into the list of u: remove the marked line adj[v].push_back(u); from the program.

A directed graph on 8 vertices with arrows 1→2, 1→3, 2→4, 3→4, 2→5, 4→6, 3→6, 6→7, 4→5, and beside it the list of each vertex: 1: 2 3; 2: 4 5; 3: 4 6; 4: 6 5; 5: empty; 6: 7; 7: empty; 8: empty.

Fig. 3. An edge goes only into the list of the vertex it leaves.

Weighted edges

When each edge has a weight, a line of the input is u v w, and each entry of a list holds a neighbour together with the weight of the edge to it, as a pair. Three places of the program change:

    // create the lists
    vector<vector<pair<int, int>>> adj(n + 1);

        int u, v, w;
        cin >> u >> v >> w;
        // add the edge to both lists
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});

        // go over the neighbours of v
        for (auto [u, w] : adj[v]) {
            cout << " (" << u << ", " << w << ")";
        }

C++

The loop for (auto [u, w] : adj[v]) (C++17) takes each pair apart: u is its .first, the neighbour, and w its .second, the weight.

The example graph with 8 vertices and each edge weight on its line, next to the adjacency list of each vertex as (neighbour, weight) pairs; vertex 4, its four edges and its list (2,2) (3,4) (6,2) (5,1) are blue.

Fig. 4. Each entry holds a neighbour and the weight of the edge to it. The edge between 4 and 6 has weight 2, so the list of 4 holds (6, 2).

A weight usually fits in int, but a sum of many weights, such as the length of a long path, often needs long long.

Examples of use

Breadth-first search and depth-first search take each vertex once and read its list once, so both run in $O (n + m)$ O(n + m).

Dijkstra's algorithm reads the weighted lists in the same way, using the weight of each entry.

A tree on $n$ vertices comes as $n - 1$ n - 1 edges and is stored in the same way. A program going down from a root meets the parent of each vertex in its list too, and skips it with if (u == parent) continue;.

Common mistakes

Adding an undirected edge to one list only, so some vertices keep empty lists though they have neighbours. Write both push_back lines.
Creating adj(n) while the vertices are numbered from 1, so an edge to vertex n writes past the end of the vector. Create adj(n + 1).
Not clearing the lists between test cases: adj.resize(n + 1) keeps the old lists. Declare adj inside the loop over tests, or call adj.assign(n + 1, {}).
Taking the size of a list as the number of different neighbours when edges can repeat. To remove repeats, sort the list, then run adj[v].erase(unique(adj[v].begin(), adj[v].end()), adj[v].end());.

Similar structures

	Adjacency list	Adjacency matrix	Edge list
Memory	$O (n + m)$ O(n + m)	$O (n^{2})$ O(n^2)	$O (m)$
Neighbours of $v$	$O (de g v)$ O(\deg v)	$O (n)$	$O (m)$
Is there an edge between $u$ and $v$ ?	$O (de g u)$ O(\deg u)	$O (1)$	$O (m)$
Add an edge	$O (1)$ on average	$O (1)$	$O (1)$

Adjacency matrix

An adjacency matrix is an $n \times n$ n \times n table: the cell in row $u$ and column $v$ is 1 if there is an edge between $u$ and $v$ , and 0 otherwise.

A table of zeros and ones with rows and columns numbered 1 to 8, and a grey unused row 0 and column 0; row 4 is shaded blue and has ones in columns 2, 3, 5 and 6, and its cell in column 7, which holds 0, has a blue frame.

Fig. 5. Row 4 has a 1 in columns 2, 3, 5 and 6, the neighbours of vertex 4. The cell in row 4, column 7 is 0.

Use it when the input already is a matrix, or for Floyd–Warshall. It needs $n^{2}$ n^2 cells, so it fits up to about 5000 vertices.

Edge list

An edge list keeps the edges as they were read, in a vector of pairs or triples. Use it when an algorithm goes over all edges in rounds, as Bellman–Ford does, or sorts them by weight, as Kruskal's algorithm does.