Graph Representations

How you store the graph decides which algorithms are cheap. Pick before you write anything else.

Representation	Space	Edge lookup	Iterate neighbours	Best for
Adjacency list	$O(n+m)$	$O(\mathrm{deg}v)$	$O(\mathrm{deg}v)$	sparse graphs — the default for DFS, BFS, Dijkstra, flows
Adjacency matrix	$O(n^2)$	$O(1)$	$O(n)$	dense graphs, small $n$ — Floyd-Warshall, Held-Karp, MPM
Edge list	$O(m)$	$O(m)$	$O(m)$	edge-sorting algorithms — Kruskal, Bellman-Ford
Implicit	$O(1)$	—	$O(\text{branching})$	grids, state spaces, game positions

Adjacency list

int n, m;
vector<vector<int>> adj(n + 1);                    // unweighted
vector<vector<pair<int,int>>> wadj(n + 1);         // {to, weight}
 
adj[u].push_back(v); adj[v].push_back(u);          // undirected
adj[u].push_back(v);                               // directed
wadj[u].push_back({v, w});                         // weighted

For very large graphs, a CSR (compressed sparse row) layout — two flat arrays head[] and nxt[], or a sorted edge array with per-vertex offsets — is 2-3× faster than vector<vector<int>> because it removes the pointer chase:

vector<int> start(n + 2, 0), to(m);
for (auto [u, v] : edges) start[u + 1]++;
for (int i = 0; i < n; i++) start[i + 1] += start[i];
vector<int> pos = start;
for (auto [u, v] : edges) to[pos[u]++] = v;
// neighbours of u: to[start[u] .. start[u+1])

Adjacency matrix

const long long INF = LLONG_MAX / 4;               // /4 so INF+INF does not overflow
vector<vector<long long>> g(n, vector<long long>(n, INF));
for (int i = 0; i < n; i++) g[i][i] = 0;

For unweighted dense graphs use bitset<N> adj[N] — neighbourhood intersections become single instructions, which is what makes Bron-Kerbosch and $O(n^3/64)$ transitive closure fast.

Edge list

struct Edge { int u, v; long long w; };
vector<Edge> edges;
sort(edges.begin(), edges.end(), [](auto& a, auto& b){ return a.w < b.w; });

Implicit graphs — the most under-used representation

Many problems are graphs that are never built. The vertices are states; the edges are moves.

Problem	Vertex	Edge
Grid maze	cell $(r,c)$	step to an adjacent free cell
Knight’s shortest path	board square	one knight move
Word ladder	a word	change one letter
Jug pouring	$(a,b)$ litres	fill / empty / pour
15-puzzle	a board configuration	slide a tile
Rubik’s cube	a cube state	one face turn
Coin change as BFS	remaining amount	subtract a coin

Write the neighbour function, not the adjacency list:

int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, 1, -1};
auto inBounds = [&](int r, int c){ return r >= 0 && c >= 0 && r < R && c < C; };

Recognising the implicit graph

If a problem asks for the minimum number of operations to transform one thing into another, and each operation is reversible or cheap to enumerate, it is a BFS on an implicit graph. This is one of the highest-value pattern recognitions in competitive programming.

Node-splitting and layered graphs

Two rewrites that turn hard constraints into ordinary graphs:

• Vertex capacities / vertex-disjoint paths → split $v$ into $v_{in}\to v_{out}$ with the capacity on the internal edge. See Suurballe.
• State-dependent movement (fuel left, keys collected, moves used mod $k$) → make the vertex a pair $(v,\text{state})$ and build a layered graph. The graph gets $k$ times bigger; the algorithm stays the same.

See also: Graph Fundamentals · Modelling Patterns