Adjacency Matrix vs. Adjacency List: Complexity Trade-offs

Introduction

In the past few lessons, we've defined what graphs are and explored the two primary ways to represent them in code: the adjacency matrix and the adjacency list. You've implemented both in C++, and you've seen that while a matrix is a simple 2D array, a list is more dynamic, storing only the connections that actually exist.

This lesson brings everything together by formally comparing these two representations. Our goal is to analyze their trade-offs in terms of time and space complexity. This analysis is not just a theoretical exercise; it is the key to deciding which tool to use for a given problem. For a competitive programmer, making the right choice here is often the difference between a solution that is accepted and one that exceeds time or memory limits.

Space Complexity: The Deciding Factor

The most significant difference between the two representations is the amount of memory they consume. Let's formalize what we've touched upon previously.

Adjacency Matrix: Requires space for a $V \times V$ matrix, regardless of how many edges are in the graph. The space complexity is therefore $O (V^{2})$ .
Adjacency List: Stores a list for each vertex. The total size is the sum of the lengths of these lists. Since each edge (u, v) adds one entry (to u's list in a directed graph) or two entries (to u's and v's lists in an undirected graph), the total number of entries stored is proportional to the number of edges, $E$ . We also need an array of size $V$ to hold the lists themselves. The space complexity is therefore $O (V + E)$ .

In competitive programming, problems often involve sparse graphs, where the number of edges $E$ is much smaller than the maximum possible number of edges, which is on the order of $V^{2}$ . For sparse graphs, $E$ is often proportional to $V$ . Think of a graph representing a road network: a city might have millions of residents (vertices), but each intersection is only connected to a handful of other intersections (edges).

To see the dramatic impact of this difference, let's consider a practical example.

Graphs

These lecture slides from the University of Texas at Arlington provide a concrete analysis of memory usage for a large, sparse graph.

Please read the section titled "Space Analysis". Focus on the calculation for a graph with 10 million vertices, where each vertex has at most 20 neighbors. The slides walk through the memory calculation for both the matrix and list representations.

As the slides demonstrate, for a graph with $V = 1 0^{7}$ and an average degree of 20, the adjacency matrix would require around 12.5 Terabytes of memory. This is far beyond the capacity of any competitive programming server (or most computers in general!). In contrast, the adjacency list would require about 3.28 Gigabytes. While still large, this is orders of magnitude more feasible.

In a typical contest, $V$ might be up to $1 0^{5}$ . An adjacency matrix would require $(1 0^{5})^{2} = 1 0^{10}$ entries, which is about 40 GB if using 4-byte integers—impossible within a 256 MB or 512 MB memory limit. An adjacency list for a sparse graph with $V = 1 0^{5}$ and $E = 2 \cdot 1 0^{5}$ would only need space for $1 0^{5} + 2 \cdot 1 0^{5}$ integers, which is easily manageable.

Time Complexity of Core Operations

Beyond space, the choice of representation affects the runtime of fundamental graph operations. There's no single "best" structure; it depends on what you need to do most often.

Let's analyze the common operations:

Operation	Adjacency Matrix	Adjacency List (`vector<vector<int>>`)	Analysis
Check for an edge `(u, v)`	$O (1)$	$O (degree (u))$	The matrix excels here; it's a direct lookup. The list requires scanning `u`'s neighbors.
Get all neighbors of `u`	$O (V)$	$O (degree (u))$	The list is far more efficient. It only iterates over actual neighbors, while the matrix must scan an entire row of size $V$ .
Add an edge `(u, v)`	$O (1)$	$O (1)$ *	Both are fast. `*`For the list, this is the amortized time for `push_back`. If you must check for duplicates first, it becomes $O (degree (u))$ .
Remove an edge `(u, v)`	$O (1)$	$O (degree (u))$	The matrix simply sets an entry to 0. The list requires finding the element `v` in `u`'s list and then removing it, which is a linear-time operation for a `vector`.

Most graph algorithms you will encounter, such as Breadth-First Search (BFS) and Depth-First Search (DFS), are built around the operation "for each neighbor of vertex u...". This is precisely where the adjacency list shines, making it the natural choice for implementing these algorithms efficiently. Using a matrix would slow these algorithms down from $O (V + E)$ to $O (V^{2})$ , which is often too slow.

The following resources provide excellent summaries and direct comparisons.

Graph Theory Introduction

This video from WilliamFiset's "Graph Theory" series provides a concise overview of the pros and cons of each representation.

Watch the segment on the adjacency matrix from the beginning, paying attention to the advantages (constant time lookup) and disadvantages (V^2 space). Then, watch the following segment on the adjacency list from here, which highlights its efficiency for sparse graphs.

For a final, clear summary in table format, the GeeksforGeeks article is an excellent reference.

Implementation of Graph in C++

This article includes a very useful table that directly contrasts the two graph representations.

Focus on the table under the heading "Difference". This table crystallizes the trade-offs we've just discussed, from memory usage to the efficiency of various operations.

A visual recap of how different graph types are represented using both an Adjacency Matrix and an Adjacency List. Notice how the matrix is always a full $V \times V$ grid, while the list's size depends on the number of actual edges.

The Competitive Programmer's Choice

So, which one should you use?

99% of the time in competitive programming, you will use an adjacency list.

The reasoning is simple and is a direct consequence of our analysis:

Memory Constraints: Problems are designed with $V$ large enough that an $O (V^{2})$ solution is almost always too memory-intensive.
Algorithmic Efficiency: The most common graph algorithms (traversals, shortest paths, etc.) depend on efficiently iterating through neighbors. The $O (degree (u))$ complexity for this operation in an adjacency list is fundamental to achieving standard algorithm runtimes like $O (V + E)$ .

The rare cases where an adjacency matrix might be considered are:

The graph is very small (e.g., $V \leq 500$ ), so $V^{2}$ is not a problem.
The graph is dense (i.e., $E$ is close to $V^{2}$ ), in which case the $O (V + E)$ space of an adjacency list offers no real advantage over $O (V^{2})$ .
The problem's logic requires many random edge existence checks, and does not heavily rely on neighbor iteration. This is characteristic of algorithms like Floyd-Warshall for all-pairs shortest paths, which we will cover much later in the course.

Conclusion

You have now completed the first module on graph fundamentals. You can define what a graph is, classify its properties, and, most importantly, represent it efficiently in C++.

Key Takeaways:

Space Complexity is the primary driver for choosing a representation. Adjacency Matrix ( $O (V^{2})$ ) is only for small or very dense graphs. Adjacency List ( $O (V + E)$ ) is ideal for the large, sparse graphs common in programming challenges.
Time Complexity trade-offs are crucial. Matrices offer $O (1)$ edge checking, while lists offer optimal $O (degree (u))$ neighbor iteration.
For almost all competitive programming scenarios, the adjacency list is the superior and default choice due to memory constraints and its synergy with core graph algorithms.

With this solid foundation in place, you are ready to move on to the next module, where we will put these data structures to work. We will begin with the two most fundamental graph algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS). These traversal techniques form the backbone of a vast number of more complex graph algorithms.

Recommended resources

Introduction

Space Complexity: The Deciding Factor

Time Complexity of Core Operations

The Competitive Programmer's Choice

Conclusion