Graph Representations

A graph $G = (V, E)$ has a set of vertices $V$ and edges $E$ between them. Edges may be directed or undirected, weighted or unweighted. The first decision in any graph problem is how to store the graph.

Adjacency list

For each vertex, store a list of its neighbors (and edge weights if any). Total space: $O(V + E)$. Iterating a vertex's neighbors is $O(\deg(v))$ — exactly the work you'd want. Checking whether a specific edge exists is $O(\deg(v))$, which can be slow.

Adjacency matrix

A $V \times V$ matrix where entry $(i, j)$ is 1 (or the weight) if there's an edge, 0 (or $\infty$) otherwise. Total space: $O(V^2)$. Edge existence check is $O(1)$. Iterating a vertex's neighbors is $O(V)$ — wasteful for sparse graphs.

Choosing between them

Use adjacency list for sparse graphs ($E \ll V^2$) and most general-purpose graph code. Use adjacency matrix when the graph is dense, when you need many edge-existence queries, or when you're running matrix algorithms (Floyd-Warshall, matrix exponentiation for path counting).

Edge list

A flat list of (u, v, weight) tuples. Useless for traversal but convenient for algorithms that process edges in sorted order (Kruskal's MST) or as input/output format.

Directed vs undirected

In an undirected graph, every edge $\{u, v\}$ shows up in both $u$'s and $v$'s adjacency list. In a directed graph, only on the source side. Be deliberate about this when reading input — bugs from "I forgot to add the reverse edge" are extremely common.

Implicit graphs

Sometimes the graph isn't stored at all — it's implicit in the problem state. A maze's grid is a graph (cells as vertices, walkable neighbors as edges). A puzzle's state space is a graph (positions as vertices, moves as edges). You compute neighbors on the fly inside your BFS/DFS rather than precomputing an adjacency list.