Graph Representations

Modelling Connections

A graph models things and the connections between them: it is a set of vertices (nodes) joined by edges. Graphs are astonishingly general — road maps, social networks, web-page links, dependency chains, and molecules are all graphs. Edges may be directed (one-way, like "A follows B") or undirected (mutual), and may carry a weight (a distance, cost, or capacity).

Two standard ways represent a graph in memory, and choosing between them is a classic space–time trade-off:

An adjacency matrix is a $V \times V$ grid where entry $(i, j)$ records whether (or how strongly) vertex $i$ connects to vertex $j$. Checking whether two specific vertices are connected is $O(1)$ — just read one cell — but the matrix always uses $O(V^2)$ space regardless of how many edges exist. It suits dense graphs (many edges).

An adjacency list stores, for each vertex, a list of its neighbors. It uses $O(V + E)$ space — proportional to the actual number of edges — and lets you efficiently iterate a vertex's neighbors, which most graph algorithms do. It suits sparse graphs (few edges), which most real graphs are. The trade-off: checking a specific edge is slower (scan the neighbor list) than the matrix's $O(1)$.

Common pitfall: using an adjacency matrix for a large sparse graph. If a million-vertex graph has only a few edges per vertex, a matrix wastes $O(V^2)$ — a trillion cells, almost all empty — while an adjacency list uses $O(V + E)$, a tiny fraction. Match the representation to the graph's density.

A small graph beside its two representations: a V×V grid mostly empty with a few accent-marked cells (matrix), and a set of short per-vertex neighbor lists (list) — the wasted cells of the sparse matrix highlighted.

$$\text{matrix } O(V^2), \;\; \text{list } O(V + E)$$