Representations of Graphs

Key Insight

Graphs can be represented using adjacency lists or adjacency matrices. Adjacency lists consist of an array `Adj` of `|V|` lists, one for each vertex, where `Adj[u]` contains all vertices `v` such that an edge `(u,v)` exists. This representation is compact and generally preferred for sparse graphs (where `|E|` is much less than `|V|²`), requiring `O(V+E)` memory. For a directed graph, the sum of adjacency list lengths is `|E|`; for an undirected graph, it is `2|E|`.

The adjacency-matrix representation uses a `|V| x |V|` matrix `A` where `a_ij = 1` if an edge `(i,j)` exists and `0` otherwise. This method is preferred for dense graphs (where `|E|` is close to `|V|²`) or when rapid determination of edge existence between two specific vertices is critical. It requires `O(V²) ` memory, regardless of the number of edges. For undirected graphs, the adjacency matrix `A` is symmetric, meaning `A = Aᵀ`.

Both adjacency lists and adjacency matrices can represent weighted graphs by storing edge weights (e.g., `w(u,v)`) within the list entry or matrix cell. Algorithms often maintain attributes for vertices (e.g., `u:color`, `u:d`) and edges (e.g., `(u,v):f`), which can be implemented using parallel arrays or object-oriented structures. While adjacency lists are asymptotically more space-efficient for sparse graphs, matrices can be simpler for small graphs and require only one bit per entry for unweighted graphs.