Graph Representations: Adjacency Matrix vs. Adjacency List

1. Representing a Graph

First, let's quickly formalize what a graph is. A graph $G$ is a pair $(V,E)$, where $V$ is a set of vertices (or nodes) and $E$ is a set of edges (or connections) between pairs of vertices.

• In an undirected graph, an edge (u, v) is the same as (v, u).
• In a directed graph, an edge (u, v) represents a one-way connection from u to v.

The challenge is how to translate this abstract structure into a concrete data structure that a program can use. The following video introduces the two primary approaches: the adjacency list and the adjacency matrix.

2. The Adjacency Matrix

As the video explained, an adjacency matrix is a straightforward representation using a two-dimensional array.

For a graph with $|V|$ vertices, we create a $|V|\times |V|$ matrix, let's call it adj. The entry adj[i][j] tells us about the edge between vertex i and vertex j.

• Structure: A |V| x |V| grid of 0s and 1s.
• Rule: adj[i][j] = 1 if an edge exists from i to j; otherwise, adj[i][j] = 0.
• Undirected Graphs: The matrix is symmetric (adj[i][j] == adj[j][i]) because an edge between i and j implies a connection in both directions.
• Weighted Graphs: Instead of 1, adj[i][j] can store the weight of the edge. A special value (like ∞ or -1) is used to indicate the absence of an edge.

The primary characteristic of an adjacency matrix is its space complexity. It always requires $O(|V{|}^2)$ space, regardless of how many edges the graph actually has. This makes it very simple to implement but can be inefficient for graphs with many vertices but few edges.

3. The Adjacency List

The adjacency list takes a more space-efficient, vertex-centric approach.

• Structure: An array (or a map/dictionary) of size $|V|$. Each entry adj[i] points to a linked list (or a dynamic array/vector) containing all the vertices j for which there is an edge from i to j.
• Undirected Graphs: If there is an edge between i and j, then j will appear in i's list, and i will appear in j's list.
• Weighted Graphs: The list can store pairs of (neighbor, weight) instead of just the neighbor vertex.

The space complexity here is directly related to the number of vertices and edges. It requires $O(|V|+|E|)$ space.

• $O(|V|)$ for the main array of pointers/lists.
• $O(|E|)$ for the total number of nodes across all linked lists. (For an undirected graph, each edge (u,v) adds two entries, one in u's list and one in v's, for a total of $2|E|$ entries, which is still $O(|E|)$).

4. Analyzing the Trade-offs

Now for the central question: which representation is better? As is often the case in software engineering, the answer is, "it depends on what you need to do." The choice involves a trade-off between space usage and the time it takes to perform certain operations.

To get a detailed breakdown of these trade-offs, let's turn to a concise textual resource.

Let's synthesize that information and highlight the most critical comparisons for algorithm design. Let deg(u) be the degree of vertex u (the number of edges connected to it).

*Adding an edge to an adjacency list is $O(1)$ if you just append to the list. The complexities for adding/removing vertices are higher for both but less commonly analyzed in basic algorithm contexts.

This table reveals two key scenarios:

1. If your algorithm needs to frequently check for the existence of arbitrary edges, an adjacency matrix is superior due to its $O(1)$ query time.
2. If your algorithm needs to iterate through the neighbors of vertices, an adjacency list is far more efficient. You only traverse the actual neighbors, not an entire row of V vertices.

This leads us to the crucial distinction between sparse and dense graphs.

• Sparse Graph: A graph with relatively few edges. Formally, $|E|\approx O(|V|)$. Most real-world graphs (social networks, road networks) are sparse. For these, the $O(|V{|}^2)$ space of a matrix is wasteful. The adjacency list is the clear winner.
• Dense Graph: A graph with many edges. Formally, $|E|\approx O(|V{|}^2)$. Here, the space complexities of both representations are asymptotically similar, so the choice may depend more on the required operations (e.g., frequent edge queries favor the matrix).

Since most graph algorithms you'll encounter (like BFS and DFS) are based on exploring a vertex's neighbors, and most problem domains involve sparse graphs, the adjacency list is the default, go-to representation for general-purpose graph programming.

Conclusion

In this lesson, we established the groundwork for our entire module on graphs. We demystified the two primary ways to store a graph in memory and, most importantly, analyzed the engineering trade-offs between them.

Key Takeaways:

• Adjacency Matrix: An $O(|V{|}^2)$ space representation that offers constant-time $O(1)$ edge existence checks. It's simple but can be very wasteful for sparse graphs.
• Adjacency List: An $O(|V|+|E|)$ space representation that excels at iterating through a vertex's neighbors in time proportional to its degree.
• Sparse vs. Dense: The choice between them hinges on the density of the graph. Sparse graphs ($|E|\ll |V{|}^2$) strongly favor adjacency lists. Dense graphs ($|E|\approx |V{|}^2$) make the adjacency matrix more viable.
• For most practical applications and the upcoming algorithms we will study, the adjacency list is the preferred representation due to its space efficiency and optimized neighbor traversal.

Preview of the Next Lesson:

Now that we know how to represent a graph, we can start exploring it. In our next lesson, we will learn our first graph traversal algorithm: Breadth-First Search (BFS). We will see how BFS systematically explores a graph level by level and how it can be used to find the shortest path between two vertices in an unweighted graph. You will see firsthand why the adjacency list's ability to efficiently retrieve neighbors is so critical for this algorithm.