Before I can run any graph algorithm, I have to decide how the graph itself is going to live in memory. That choice sounds trivial, but it quietly determines the performance ceiling of everything built on top of it. This guide is my rundown of the elementary ways to represent graphs — adjacency matrices, adjacency lists, and edge lists — along with the reasoning I use to pick between them and the basic operations built on top of each.
History and Background
Graph theory itself dates back to Leonhard Euler’s 1736 solution to the Seven Bridges of Königsberg problem, which is generally credited as the founding moment of the field. But representing graphs computationally is a much newer concern, tied to the rise of digital computing in the mid-20th century. Adjacency matrices arose naturally from linear algebra’s treatment of graphs (a graph’s matrix representation makes eigenvalue-based analysis possible), while adjacency lists became popular as computer scientists needed more memory-efficient structures for the large, sparse graphs that show up in real-world networks. Both representations were standardized in early algorithms texts and are foundational material in CLRS.
Problem Statement
Given a set of vertices and edges, I need a data structure that supports the operations graph algorithms actually need: checking if an edge exists, iterating over a vertex’s neighbors, adding/removing edges, and doing all of this efficiently for the graph’s actual density (sparse vs. dense).
Core Concepts
- Vertex (Node): A basic unit representing an entity.
- Edge: A connection between two vertices; can be directed or undirected, weighted or unweighted.
- Degree: Number of edges incident on a vertex (in-degree/out-degree for directed graphs).
- Sparse graph: |E| is much smaller than |V|².
- Dense graph: |E| is close to |V|².
- Weighted graph: Edges carry numeric costs.
- Simple graph: No self-loops or multiple edges between the same pair of vertices.
How It Works
Graphs are typically represented one of three ways:
- Adjacency Matrix: A V × V matrix where cell [i][j] holds 1 (or the weight) if an edge exists from i to j, and 0/infinity otherwise.
- Adjacency List: An array of V lists, where list[i] contains all vertices adjacent to vertex i.
- Edge List: A simple list of all edges as (u, v) or (u, v, weight) tuples, with no per-vertex indexing.
Choosing between them is really a tradeoff between the speed of edge lookup, the speed of neighbor iteration, and the memory used, which strongly depends on how sparse or dense the graph is.
Working Principle
The adjacency matrix leans entirely on direct indexing: checking or setting an edge is a single array access, which is why it’s O(1) for edge queries. Its downside is that it always allocates V² space no matter how many actual edges exist, and iterating over a vertex’s neighbors always costs O(V) since I have to scan the whole row.
The adjacency list instead stores only the edges that actually exist, using a per-vertex list (often a linked list, dynamic array, or even a hash set). This makes it far more memory-efficient for sparse graphs and makes neighbor iteration proportional to the vertex’s actual degree rather than the total vertex count — but checking whether a specific edge exists now requires scanning a list rather than a direct lookup (unless I use a hash-based list).
The edge list is the simplest and is mostly useful when I need to process all edges globally rather than per-vertex — for example, sorting edges by weight for Kruskal’s algorithm.
Mathematical Foundation
For an adjacency matrix, space usage is:
$$S_{matrix} = O(V^2)$$
For an adjacency list, space usage is:
$$S_{list} = O(V + E)$$
Since a simple graph has at most:
$$E_{max} = \binom{V}{2} = \frac{V(V-1)}{2}$$
edges, the adjacency list only becomes worse than the matrix when the graph approaches this maximum density, i.e., when E is on the order of V². This is the formal justification for the common rule of thumb: use adjacency lists for sparse graphs, matrices for dense ones.
Diagrams
flowchart TD
A[Choose Graph Representation] --> B{Is the graph dense E close to V squared?}
B -- Yes --> C[Use Adjacency Matrix: O1 edge lookup]
B -- No --> D{Do I need fast edge existence checks?}
D -- Yes --> E[Use Adjacency List with hash set per vertex]
D -- No --> F[Use plain Adjacency List]
C --> G[Proceed with graph algorithm]
E --> G
F --> G
Pseudocode
// Adjacency Matrix
CREATE-MATRIX(V):
matrix = V x V array initialized to 0
return matrix
ADD-EDGE-MATRIX(matrix, u, v, weight):
matrix[u][v] = weight
matrix[v][u] = weight // omit for directed graphs
// Adjacency List
CREATE-LIST(V):
adj = array of V empty lists
return adj
ADD-EDGE-LIST(adj, u, v, weight):
adj[u].append((v, weight))
adj[v].append((u, weight)) // omit for directed graphs
Step-by-Step Example
Consider an undirected graph with vertices {0,1,2,3} and edges (0,1), (0,2), (1,3).
As an adjacency matrix:
0 1 2 3
0 [ 0 1 1 0 ]
1 [ 1 0 0 1 ]
2 [ 1 0 0 0 ]
3 [ 0 1 0 0 ]
As an adjacency list:
0: [1, 2]
1: [0, 3]
2: [0]
3: [1]
As an edge list:
(0,1), (0,2), (1,3)
Each representation stores exactly the same graph, but querying “are 0 and 3 connected?” is O(1) with the matrix (a single lookup at [0][3]) versus O(degree(0)) with the list (I’d scan 0’s list, which has 2 entries).
Time Complexity
| Operation | Adjacency Matrix | Adjacency List |
|---|---|---|
| Check edge (u,v) exists | O(1) | O(degree(u)) |
| Iterate all neighbors of u | O(V) | O(degree(u)) |
| Add edge | O(1) | O(1) |
| Remove edge | O(1) | O(degree(u)) |
| Iterate all edges | O(V²) | O(V + E) |
Space Complexity
- Adjacency Matrix: O(V²), regardless of how many edges actually exist.
- Adjacency List: O(V + E), scaling with actual graph density.
- Edge List: O(E), the most compact for edge-centric algorithms but the worst for neighbor queries since it has no per-vertex indexing at all.
Correctness Analysis
Correctness here isn’t really about a single algorithm but about whether the representation faithfully preserves the graph’s structure: every representation must guarantee that for every edge (u,v) in E, a query for that edge returns true (or the correct weight), and that iterating a vertex’s neighbor set returns exactly its adjacent vertices, no more and no less. All three standard representations satisfy this trivially by construction, assuming edges are inserted correctly and, for undirected graphs, inserted symmetrically.
Advantages
Adjacency Matrix:
- O(1) edge existence checks.
- Simple to implement, especially for dense or small graphs.
- Works naturally with linear algebra techniques (matrix powers for path counting, spectral graph theory).
Adjacency List:
- Much more memory-efficient for sparse graphs, which is the overwhelmingly common case in real-world networks.
- Faster neighbor iteration, which speeds up BFS/DFS considerably on sparse graphs.
Disadvantages
Adjacency Matrix:
- Wastes huge amounts of memory on sparse graphs.
- Iterating over all edges takes O(V²) regardless of actual edge count.
Adjacency List:
- Edge existence check is slower unless paired with a hash set.
- Slightly more complex to implement, especially when edges need to be removed efficiently.
Applications
- Adjacency matrices are common in dense graph problems, spectral clustering, and algorithms like Floyd-Warshall that naturally operate on matrix-shaped data.
- Adjacency lists are the default choice for BFS, DFS, Dijkstra’s, and most real-world graph processing since real-world graphs (social networks, road networks, the web graph) are almost always sparse.
- Edge lists are the natural fit for Kruskal’s MST algorithm, since it processes edges in sorted order regardless of which vertex they belong to.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#define MAX_V 100
/* Adjacency Matrix representation */
typedef struct {
int matrix[MAX_V][MAX_V];
int V;
} GraphMatrix;
void initMatrix(GraphMatrix *g, int v) {
g->V = v;
for (int i = 0; i < v; i++)
for (int j = 0; j < v; j++)
g->matrix[i][j] = 0;
}
void addEdgeMatrix(GraphMatrix *g, int u, int v) {
g->matrix[u][v] = 1;
g->matrix[v][u] = 1;
}
/* Adjacency List representation using linked lists */
typedef struct Node {
int vertex;
struct Node *next;
} Node;
typedef struct {
Node *head[MAX_V];
int V;
} GraphList;
void initList(GraphList *g, int v) {
g->V = v;
for (int i = 0; i < v; i++)
g->head[i] = NULL;
}
void addEdgeList(GraphList *g, int u, int v) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = g->head[u];
g->head[u] = newNode;
newNode = (Node *)malloc(sizeof(Node));
newNode->vertex = u;
newNode->next = g->head[v];
g->head[v] = newNode;
}
void printList(GraphList *g) {
for (int i = 0; i < g->V; i++) {
printf("%d: ", i);
Node *temp = g->head[i];
while (temp != NULL) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("NULL\n");
}
}
int main(void) {
GraphMatrix gm;
initMatrix(&gm, 4);
addEdgeMatrix(&gm, 0, 1);
addEdgeMatrix(&gm, 0, 2);
addEdgeMatrix(&gm, 1, 3);
printf("Adjacency Matrix:\n");
for (int i = 0; i < gm.V; i++) {
for (int j = 0; j < gm.V; j++)
printf("%d ", gm.matrix[i][j]);
printf("\n");
}
GraphList gl;
initList(&gl, 4);
addEdgeList(&gl, 0, 1);
addEdgeList(&gl, 0, 2);
addEdgeList(&gl, 1, 3);
printf("\nAdjacency List:\n");
printList(&gl);
return 0;
}
Sample Input and Output
Input: Vertices {0,1,2,3}, edges (0,1), (0,2), (1,3).
Output:
Adjacency Matrix:
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0
Adjacency List:
0: 2 -> 1 -> NULL
1: 3 -> 0 -> NULL
2: 0 -> NULL
3: 1 -> NULL
Optimization Techniques
- Hybrid representation: Use an adjacency list for iteration but back each vertex’s neighbor set with a hash set for O(1) average-case edge existence checks.
- CSR (Compressed Sparse Row) format: A flattened, array-based version of adjacency lists that’s extremely cache-friendly and widely used in high-performance and GPU graph processing.
- Bitset rows for adjacency matrices: Packing each row into bits instead of bytes/ints cuts memory usage by up to 32x-64x and speeds up bitwise set operations for tasks like clique detection.
- Dynamic arrays instead of linked lists: Using resizable arrays for adjacency lists improves cache locality compared to pointer-chasing linked lists, often giving a meaningful real-world speedup.
Common Mistakes
- Choosing an adjacency matrix for a large sparse graph, silently wasting enormous amounts of memory or blowing the memory budget entirely.
- Forgetting to add both directions when representing an undirected graph.
- Not freeing dynamically allocated adjacency list nodes in C, leading to memory leaks.
- Mixing up 0-indexed and 1-indexed vertices between input and internal storage.
- Assuming edge list iteration is fast for neighbor queries, when it actually requires a full O(E) scan without additional indexing.
Further Reading
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 3rd/4th Edition, MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Even, S. — Graph Algorithms, 2nd Edition, Cambridge University Press: https://www.cambridge.org/core/books/graph-algorithms/
- GeeksforGeeks, Graph and its representations: https://www.geeksforgeeks.org/graph-and-its-representations/
- Stanford CS161 Lecture Notes: https://web.stanford.edu/class/cs161/
- Compressed Sparse Row format reference, NIST: https://mathworld.wolfram.com/SparseMatrix.html
