Graph Representation
Graph Representation
Definition: Data structures used to represent graphs consisting of vertices (nodes) and edges (connections), primarily Adjacency Matrix and Adjacency List.
How It Works
Adjacency Matrix: a 2D array of size V x V, where matrix[i][j] stores whether (and how heavily) vertex i connects to vertex j.
A B C
A [ 0 1 1 ]
B [ 1 0 1 ]
C [ 1 1 0 ]Checking or setting a specific edge is O(1) direct array access, but the structure always costs O(V^2) space regardless of how many edges actually exist, making it wasteful for sparse graphs.
Adjacency List: an array or map where index/key u stores the list of u’s neighbors.
A: [B, C]
B: [A, C]
C: [A, B]Space is O(V + E), proportional to what’s actually in the graph, and listing all neighbors of a node takes O(degree(u)) time rather than a full O(V) scan of a matrix row. This is the default choice for most real-world graphs.
Edge List: a flat list of (u, v, weight) tuples. It uses minimal O(E) space and is the simplest to sort, which is exactly why it’s the natural representation for edge-order-dependent algorithms like Kruskal’s minimum spanning tree, where edges must be processed in ascending weight order.
Directed vs. undirected graphs affect representation symmetry: an undirected edge u-v appears twice in an adjacency list (once under u’s neighbors, once under v’s) or as a symmetric pair of entries in the matrix. Weighted graphs replace the boolean matrix entry (or list membership) with a numeric weight, using infinity or 0 in the matrix to denote “no edge” depending on convention.
Building a Weighted Directed Graph, Both Forms
For the directed weighted edges A->B(5), A->C(2), B->C(1):
Adjacency List (weighted): Adjacency Matrix (weighted, inf = no edge):
A: [(B,5), (C,2)] A B C
B: [(C,1)] A [ 0 5 2 ]
C: [] B [ inf 0 1 ]
C [ inf inf 0 ]Note the asymmetry: C has no outgoing edges in either representation, but both B and A list edges pointing to C. A directed graph’s adjacency list only records outgoing edges per node; finding all edges pointing into a node requires either scanning every other node’s list (O(V+E)) or maintaining a separate reverse adjacency list built alongside the forward one.
Complexity Analysis
| Operation | Adjacency Matrix | Adjacency List | Edge List |
|---|---|---|---|
| Space | O(V^2) | O(V + E) | O(E) |
| Check if edge (u,v) exists | O(1) | O(degree(u)) | O(E) |
| Iterate all neighbors of u | O(V) | O(degree(u)) | O(E) |
| Add an edge | O(1) | O(1) | O(1) |
| Iterate all edges | O(V^2) | O(V + E) | O(E) |
Why It Matters
- Choosing the right graph representation directly determines the time and memory efficiency of every algorithm run on top of it; the same Dijkstra Algorithm runs in O(V^2) on a matrix versus O((V+E) log V) on an adjacency list paired with a heap.
- Adjacency lists are the default choice in most real-world graphs, social networks, road networks, dependency graphs, because those graphs are naturally sparse: average node degree is small relative to the total node count, so the O(V+E) space stays close to O(V).
- Matrix representation enables fast algebraic graph algorithms, e.g. counting paths of length k via matrix exponentiation, or all-pairs reachability via Boolean matrix multiplication, that adjacency lists can’t express as directly.
Common Pitfalls
- Using an Adjacency Matrix on massive sparse graphs wastes enormous memory on zero-entries; a 1-million-node social graph would need a 10^12-cell matrix, which is infeasible to even allocate.
- Forgetting to add both directions for an undirected edge in an adjacency list causes traversal algorithms to silently miss valid paths, since a neighbor relationship that exists logically may only be recorded from one side.
- Choosing an Adjacency Matrix when the algorithm’s dominant cost is “iterate over all neighbors of a node,” as in BFS/DFS, turns an O(degree) operation into an unnecessary O(V) scan per node, inflating overall traversal from O(V+E) to O(V^2).
- Not accounting for self-loops or multi-edges (parallel edges between the same two nodes) when the chosen representation and downstream algorithm both assume a simple graph.
- Storing weighted-graph “no edge” as
0in a matrix when0is also a legitimate edge weight, creating ambiguity that silently corrupts shortest-path calculations;infinity(or a sentinel) avoids the collision.
Comparison
| Adjacency Matrix | Adjacency List | Edge List | |
|---|---|---|---|
| Best for | Dense graphs, algebraic operations | Sparse graphs (most real-world graphs) | Edge-order algorithms (Kruskal’s) |
| Edge existence check | O(1) | O(degree(u)) | O(E) |
| Memory efficiency on sparse graphs | Poor | Excellent | Excellent |
| Ease of sorting edges by weight | Awkward | Awkward | Natural |
| Cache locality | Excellent (flat array) | Poor for list-of-lists, good for CSR | Excellent (flat array) |
| Typical library default | Rarely used raw | Map<Node, List<Node>> or similar | Used mainly as input format for edge-based algorithms |
Example
Social networks with millions of users use adjacency lists because each user connects to only a tiny fraction of the total user base. For the graph A-B, A-C, B-C:
Adjacency List: Adjacency Matrix:
A: [B, C] A B C
B: [A, C] A [ 0 1 1 ]
C: [A, B] B [ 1 0 1 ]
C [ 1 1 0 ]The list uses 6 total entries; the matrix uses 9 cells, 3 of them wasted on the diagonal. The gap widens dramatically as graphs scale: a graph with 1 million nodes and an average of 50 connections each needs roughly 50 million adjacency-list entries, versus 10^12 matrix cells, most of them zero.
Other Representations
- Adjacency Set: like an adjacency list, but each node’s neighbors are stored in a hash set instead of a list, trading a small constant-factor memory increase for O(1) average edge-existence checks instead of O(degree(u)).
- Compressed Sparse Row (CSR): a flattened array-based encoding of an adjacency list, used heavily in high-performance and GPU graph libraries, storing all neighbor lists concatenated in one array plus an offset array marking where each node’s neighbors start. This trades flexibility (no easy insertion) for extremely compact, cache-friendly storage.
- Implicit graphs: many graphs, like a grid, a chessboard, or a state-transition graph in a puzzle, are never materialized as an explicit structure at all; neighbors are computed on demand from a node’s coordinates or state, avoiding the memory cost of any explicit representation entirely.
FAQ
Which representation should I default to? Adjacency list, unless the graph is known to be dense (E close to V^2) or the algorithm specifically needs O(1) edge-existence checks or algebraic operations like matrix exponentiation.
Does the representation affect correctness, not just performance? Generally no, the same algorithm produces the same result regardless of representation, but performance differences can be so large (O(V) vs O(degree(u)) per neighbor lookup) that an algorithm which is theoretically correct becomes practically unusable on the wrong representation at scale.
Common Interview Questions
- How would you detect whether a graph is dense or sparse before choosing a representation? — compare edge count E to V^2; if E is a small fraction of V^2 (e.g. average degree well under V), the graph is sparse and an adjacency list wins on memory without sacrificing much speed.
- Why does an adjacency matrix make matrix-power-based path counting possible? — because matrix multiplication of the adjacency matrix with itself counts walks of length 2 between every pair of nodes, and repeated multiplication (matrix exponentiation) generalizes this to walks of any fixed length, a computation with no natural equivalent on an adjacency list.
- How would you represent a weighted, directed multigraph (multiple parallel edges allowed)? — an adjacency list where each entry is itself a list of
(neighbor, weight)pairs rather than a single weight per neighbor, since a plain matrix or single-weight list can’t distinguish multiple parallel edges between the same two nodes.
Real-World Systems
- Social graph platforms store connections as adjacency lists (often sharded across many machines by user ID), since the graph is enormous and sparse, and most queries only need one user’s immediate neighbors.
- Graph databases like Neo4j use a variant of the adjacency list internally, “index-free adjacency,” where each node stores direct pointers to its relationship records, so traversing to a neighbor is a pointer dereference rather than an index lookup or join.
- Route-planning and GIS systems represent road networks as weighted adjacency lists (or CSR for performance-critical routing engines), since intersections typically connect to only a handful of other intersections, making the graph highly sparse.
- Scientific computing and graph-analytics frameworks (e.g. large-scale PageRank-style computations) commonly use Compressed Sparse Row layouts specifically because it maximizes cache locality and vectorization opportunities during bulk operations over millions of nodes.
Related Terms
Referenced by