Adjacency List Basics
An array of vectors — adj[u] contains all neighbours of node u. For weighted graphs, store pairs of (neighbour, weight).
C++ — adjacency list
int n = 5;
vector> adj(n); // unweighted
// or: vector>> adj(n); // weighted
// Add edge u↔v (undirected)
adj[u].push_back(v);
adj[v].push_back(u);
// Add edge u→v (directed)
adj[u].push_back(v);
// Iterate neighbours
for (int v : adj[u]) { /* ... */ }
Rust — adjacency list
let n = 5;
let mut adj: Vec> = vec![vec![]; n];
adj[u].push(v);
adj[v].push(u);
for &v in &adj[u] { /* ... */ }
💡 O(V+E) memory — the gold standard
Adjacency list uses O(V+E) memory — proportional to actual edges. Sparse graphs (E ≈ V) use almost no memory. Always prefer this over adjacency matrix unless the graph is tiny and dense.