Graph Representations

A graph is an abstract relation; an adjacency list or matrix is an implementation decision. That decision is observable: it determines whether checking one edge is cheap, whether scanning neighbors touches only real edges, whether vertex deletion invalidates identifiers, and whether a traversal costs $O(V+E)$ or $O(V^2)$. The right representation follows from the graph’s semantics and workload, not from a slogan about sparse versus dense graphs.

Specify the graph before storing it #

That minimal definition leaves choices that a data structure cannot guess:

A simple directed graph treats $(u,v)$ as either present or absent. A directed multigraph can contain several edges with the same endpoints; those edges need their own identities or keys. A weight belongs to an edge, not to the mathematical notion of adjacency itself.

Vertex identity also needs a contract. An integer index is compact and directly addresses arrays. A string or object key is stable and descriptive but requires a map. Payload—names, colors, capacities, timestamps—should remain conceptually distinct from identity even when a library stores both in one object.

Choose from operations, not density alone #

Before selecting a structure, list what clients actually do:

• enumerate vertices or all edges;
• test whether $(u,v)$ exists;
• iterate outgoing or incoming edges of one vertex;
• add or remove edges and vertices;
• attach or update edge properties;
• preserve parallel-edge identity or neighbor order;
• run matrix algebra or adjacency-based algorithms.

The same graph can favor different structures in different phases. A loader may accept an edge stream, canonicalize it into CSR for repeated analytics, and maintain a separate mutable overlay for updates. That is a deliberate multi-representation design, not evidence that one representation was “wrong.”

The examples below use this independently defined directed weighted graph:

flowchart LR
  A((A)) -->|"4"| B((B))
  A -->|"1"| D((D))
  D -->|"2"| C((C))
  C -->|"1"| B
  B -->|"3"| E((E))
  C -->|"5"| E

The fixed vertex order is $[A,B,C,D,E]$, mapped to indices $[0,1,2,3,4]$. The order is metadata required by array representations; it is not an intrinsic property of the abstract graph.

Edge lists: preserve edge records directly #

The bare edge-list representation is simply a sequence of endpoint records:

The structure stores $\Theta(E)$ edge records and is natural for streaming input, sorting, serialization, and algorithms that inspect every edge. A bare edge list does not encode isolated vertices, so a complete representation must also store the vertex universe unless the contract defines $V$ to be exactly the endpoints appearing in the stream. Its other weakness is local adjacency: without an index, finding all outgoing edges of C or testing D→B scans up to all $E$ records.

An edge list handles a multigraph naturally if records keep distinct edge IDs. But duplicate endpoint pairs have no automatic meaning. They might be:

• genuine parallel edges;
• accidental duplicate input;
• coordinate contributions intended to be summed;
• successive updates where only the last should survive.

Canonicalization must choose one meaning. Silently deduplicating changes a multigraph; silently summing changes edge weights.

Sorting the records by source groups outgoing edges and is the first step toward an adjacency array or CSR. Adding an index from each source to its group turns the bare edge list into a richer structure with different costs.

Adjacency matrices: index every possible pair #

Let $n=|V|$ and choose a bijection $\iota:V\to\{0,\ldots,n-1\}$. A presence matrix $A$ has

$$A_{ij}= \begin{cases} 1 & \text{if }(\iota^{-1}(i),\iota^{-1}(j))\in E,\\ 0 & \text{otherwise.} \end{cases}$$

For the example, a weight matrix can use · for “no edge”:

The matrix allocates $n^2$ logical cells whether the graph contains zero edges or all possible edges. This yields a direct trade:

• edge lookup, insertion, or deletion at known indices: $O(1)$ cell access;
• outgoing-neighbor enumeration: scan one row, $\Theta(V)$;
• incoming-neighbor enumeration: scan one column, $\Theta(V)$;
• storage: $\Theta(V^2)$ cells.

Bit packing can reduce an unweighted matrix to roughly $n^2$ bits, but a numeric matrix, object matrix, or row-array implementation uses larger cells and alignment. Big-O describes growth, not actual bytes.

For an undirected simple graph the matrix is symmetric: $A_{ij}=A_{ji}$. A loop occupies a diagonal cell. A directed matrix is not symmetric, and the source/target orientation must be labeled—some APIs choose rows as sources, while a transposed convention is mathematically possible.

Matrices are compelling when the graph is dense, the vertex set is fixed, constant-time pair lookup dominates, or the algorithm is naturally algebraic. They are wasteful for a huge sparse graph whose algorithms only scan real neighbors.

Adjacency lists are a family, not one complexity #

An adjacency-list representation maps each vertex to a collection of its outgoing edges:

For a directed graph stored by outgoing incidences,

$$\sum_{v\in V}\mathop{\mathrm{outdeg}}(v)=|E|.$$

For a loop-free undirected graph stored in both endpoints’ lists,

$$\sum_{v\in V}\deg(v)=2|E|.$$

Thus the outer vertex structure plus all adjacency records uses $\Theta(V+E)$ logical storage. The constant factors depend on whether an undirected edge is one object referenced twice or two copied records.

The inner collection determines the operation costs:

There is therefore no representation-independent statement that “adjacency-list lookup is $O(1)$.” Neighbor iteration is degree-proportional; pair membership depends on the chosen inner container.

Arrays often have excellent locality and low per-edge overhead. Trees and hash tables spend more metadata to accelerate membership or enforce uniqueness. A library such as Boost.Graph exposes these choices because the best container follows from the workload.

Outgoing versus incoming adjacency #

Storing only outgoing lists makes out_edges(u) efficient but may require scanning the entire graph for in_edges(u). A bidirectional representation keeps both indexes:

$$(u,v)\in out[u] \quad\Longleftrightarrow\quad (u,v)\in in[v].$$

That equivalence is a mutation invariant. Insertion and deletion must update both sides atomically. The reward is efficient predecessor traversal; the cost is extra storage and write work.

For an undirected graph, storing each edge under both endpoints creates a similar twin-incidence invariant. Self-loops require a declared convention: store one incidence or two, and define degree consistently.

Vertex descriptors can be fragile #

If array position is the vertex ID, removing vertex 2 by compacting the array can renumber every later vertex and force endpoint rewrites throughout the graph. Stable external IDs avoid that semantic change but need a map to compact internal indices. A robust system often separates:

• stable application key;
• dense internal index;
• vertex payload.

CSR compacts static adjacency #

Compressed Sparse Row (CSR) is an array layout for row-grouped nonzero entries. Applied to a directed adjacency matrix, it is a compact, usually static adjacency list with three arrays:

• indptr: where each vertex’s row starts;
• indices: target vertex indices;
• data: weights or other scalar values aligned with indices.

For the example graph, with records sorted by source:

Vertex $u$ owns the half-open slice

$$indices[indptr[u]:indptr[u+1]],$$

with the same slice in data. For C, index 2, the slice is positions [3:5]: targets [1,4], or B and E, with weights [1,5].

The essential CSR invariants are:

1. indptr has length $V+1$;
2. indptr[0]=0 and pointers are nondecreasing;
3. indptr[V] equals the stored-entry count;
4. indices and data are aligned;
5. every target index is in range;
6. if canonical sorted rows are promised, indices are sorted and duplicate-free within each row.

Locating a row’s slice is $O(1)$, and scanning it is $\Theta(\deg^+(u))$ with contiguous memory. Membership is not automatically constant-time: it is a row scan, or $O(\log\deg^+(u))$ binary search if indices are sorted.

Structural insertion into the middle of packed arrays may shift many later entries and adjust later row pointers. CSR therefore excels when topology is stable and reads dominate. Build in a mutation-friendly form, then compact; or rebuild deliberately after a batch of changes.

Compressed Sparse Column (CSC) is the transposed layout and favors incoming/column access. Keeping both CSR and CSC duplicates index information but makes both directions compact.

Properties and multigraphs need explicit schemas #

Many libraries attach dictionaries or property maps to vertices and edges. NetworkX, for example, distinguishes simple directed/undirected classes from multi-edge classes and stores adjacency through nested mappings. That concrete API illustrates a general rule: topology, identity, and attributes are separate contracts even if one structure hosts all three.

For a multigraph, adj[u][v] = weight is insufficient because one scalar cannot represent several edge identities. Choices include:

• adj[u][v] is a map from edge key to properties;
• adjacency stores edge IDs, and a separate edge table owns endpoints/properties;
• parallel edges are deliberately aggregated by min, sum, or another domain rule;
• insertion rejects a second edge.

Aggregation is safe only when it preserves the downstream question. Replacing parallel weighted edges by their minimum may preserve ordinary shortest distances, but it destroys edge identity and is not valid for capacity sums, audit records, or disjoint-path questions.

Conversion is a semantic operation #

Changing layout requires more decisions than copying values:

Edge list to adjacency list or CSR #

1. Validate that every endpoint belongs to the vertex universe.
2. Choose and record a vertex-to-index mapping.
3. Decide what duplicate endpoint pairs mean.
4. Group or sort by source.
5. Build adjacency containers or count rows and prefix-sum into CSR pointers.
6. Preserve edge IDs and attributes, or document intentional loss.

Adjacency list to matrix #

1. Choose a fixed vertex order.
2. Choose presence encoding separately from weight values.
3. Decide how parallel edges map to one cell—or reject the conversion.
4. For undirected data, decide whether to validate symmetry or create it.

Matrix or CSR back to a graph #

1. Distinguish implicit absence from explicit zero.
2. Preserve row/column orientation.
3. Restore the vertex-index mapping.
4. Treat symmetry as a declared undirected convention, not an accidental observation.

Representation changes algorithm cost #

A traversal that asks for every outgoing neighbor of every reached vertex behaves differently over two representations:

• adjacency iteration scans each stored incidence once, leading to $O(V+E)$ for BFS or DFS;
• a matrix scans a $V$-cell row for each reached vertex, leading to $O(V^2)$ in the worst case even when $E$ is small.

The algorithm did not change. Its primitive out_neighbors(u) did. Complexity must therefore name both the abstract algorithm and the representation providing its operations.

The same principle applies to updates and all-pairs queries. Matrix edge membership is directly indexed; a sequence adjacency list may scan a high-degree row; a hash adjacency map trades memory and hashing for expected lookup. There is no universal winner.

Selection guide #

An implicit graph may never materialize $E$ at all: a state and a successor function define neighbors on demand. Search problems often need this because the full state space is too large. The cost model then includes neighbor generation and state canonicalization, while the same abstract traversal interface can still apply.

Failure diagnostics #

When graph behavior or performance is surprising, inspect:

1. Is the graph directed, simple, loop-enabled, weighted, or multi-edge?
2. What exactly is a vertex descriptor, and can mutation invalidate it?
3. Does adjacency store targets, edge IDs, or property records?
4. Is incoming adjacency indexed or reconstructed by scanning?
5. How are zero weights, missing weights, and duplicate coordinates represented?
6. Does iteration order have a contract, or is an algorithm accidentally relying on a container artifact?
7. Which primitive operation dominates the algorithm, and what does this representation charge for it?
8. Did a conversion preserve direction, multiplicity, identity, attributes, and explicit zeros?

Exercises #

1. For the example graph, answer out_neighbors(C), in_neighbors(B), and has_edge(D,B) from each representation. State the work required, not only the answer.
2. Add E→A with weight 0. Show why a dense numeric matrix initialized with zeros is ambiguous, and propose two lossless encodings.
3. Insert a second edge A→B with weight 7. Describe one lossless adjacency representation and one deliberate aggregation that would preserve ordinary shortest-distance queries but not edge identity.
4. Derive the CSR arrays after adding E→A(0) while keeping targets sorted within each row.
5. A directed graph has $10^6$ vertices and $3\times10^6$ edges. Compare logical cell/record counts for a matrix and outgoing adjacency representation. Do not guess physical bytes.
6. Explain why BFS over an adjacency matrix can cost $\Theta(V^2)$ even when it reaches only a graph with $E=\Theta(V)$.