Graph Representations: Adjacency Lists vs. Matrices

1. The Five Concepts for Today

We will break down today's topic into five interrelated concepts, moving from foundational definitions to deep trade-off analysis:

1. What is a Graph? The basic vocabulary of nodes, edges, and their properties.
2. Adjacency Matrix: Representing connections in a grid.
3. Adjacency List: Representing connections as lists of neighbors.
4. Space Complexity Trade-offs: The "Sparse vs. Dense" dilemma.
5. Time Complexity Trade-offs: Analyzing the performance of key operations.

Concept 1: What is a Graph?

Technical Explanation

A graph $G$ is a data structure used to represent relationships or connections between objects. It's formally defined as a pair of sets, $G=(V,E)$, where:

• $V$ is a set of vertices (or nodes), which represent the objects.
• $E$ is a set of edges, which represent the connections between pairs of vertices.

Graphs can have several properties:

• Directed vs. Undirected: An undirected edge (u, v) implies a two-way relationship (like a friendship on Facebook). A directed edge (u, v) implies a one-way relationship (like following someone on Twitter).
• Weighted vs. Unweighted: A weighted edge has a "cost" or "distance" associated with it (like the distance between two cities on a map). In an unweighted graph, all edges are considered equal.
• Cyclic vs. Acyclic: A cycle is a path that starts and ends at the same vertex.

For a great overview of this terminology and its relevance, the following resource is very helpful.

Metaphor: A Road Map

Think of a graph as a road map.

• Vertices (Nodes) are the cities.
• Edges are the roads connecting the cities.
• An undirected graph is like a map with all two-way streets.
• A directed graph is like a map with one-way streets.
• A weighted graph shows the distance (weight) of each road. An unweighted graph just shows that a road exists, not how long it is.

Concept 2: The Adjacency Matrix

Technical Explanation

An adjacency matrix is one of the simplest ways to represent a graph. For a graph with $|V|$ vertices, we use a $|V|\times |V|$ matrix (a 2D array). Let's call it adj.

• For an unweighted graph, adj[i][j] = 1 if there's an edge from vertex i to vertex j, and 0 otherwise.
• For a weighted graph, adj[i][j] = w if an edge with weight w exists, and often 0 or ∞ if it doesn't.
• In an undirected graph, the matrix is symmetric because an edge from i to j implies an edge from j to i, so adj[i][j] = adj[j][i].

Metaphor: An Airline Flight Chart

Imagine a giant chart at an airport listing all possible departure cities as rows and all possible arrival cities as columns. A checkmark (or a flight price) in the cell at (row_i, col_j) means there is a direct flight from city i to city j. If you're checking for a flight, you can find the answer almost instantly by looking at the specific cell.

Python Code: Adjacency Matrix

Here’s how you could build an adjacency matrix in Python for an unweighted, undirected graph with 4 vertices.

# Assume vertices are 0, 1, 2, 3
num_vertices = 4
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]

# Initialize a V x V matrix with zeros
adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

# Populate the matrix based on the edges
for u, v in edges:
    # For an undirected graph, the connection is two-way
    adj_matrix[u][v] = 1
    adj_matrix[v][u] = 1

# Print the resulting matrix
for row in adj_matrix:
    print(row)
# Output:
# [0, 1, 1, 0]
# [1, 0, 1, 0]
# [1, 1, 0, 1]
# [0, 0, 1, 0]

Concept 3: The Adjacency List

Technical Explanation

The adjacency list is the most common way to represent graphs in practice, especially for interview problems. It consists of an array or hash map where the index or key corresponds to a vertex. The value stored at that location is a list (or other collection) of its adjacent vertices.

• For a graph with $|V|$ vertices, you have an array of $|V|$ lists.
• adj[i] contains a list of all vertices j such that there is an edge from i to j.
• For a weighted graph, the list stores pairs: (neighbor_vertex, weight).

To see a clear, step-by-step construction of both adjacency matrices and lists, the following video is excellent.

Metaphor: A Smartphone's Contact List

An adjacency list is like your phone's contact list. Each person in your contacts is a "vertex." When you tap on a person's name, you see a list of their specific friends that you also have in your contacts—their "neighbors." You don't have a giant list of every person in the world with checkboxes for who is and isn't a friend; you only store the connections that actually exist.

Python Code: Adjacency List

Using a dictionary in Python is a very flexible way to implement an adjacency list, as it doesn't require vertices to be numbered contiguously from 0.

from collections import defaultdict

# Assume vertices can be any hashable type, e.g., numbers or strings
num_vertices = 4
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]

# Use a defaultdict to easily append to lists for new keys
adj_list = defaultdict(list)

# Populate the list
for u, v in edges:
    # For an undirected graph, add edges in both directions
    adj_list[u].append(v)
    adj_list[v].append(u)

# Print the resulting dictionary
# Note: defaultdict will only show keys that were added
for vertex in range(num_vertices):
    print(f"{vertex}: {adj_list[vertex]}")
# Output:
# 0: [1, 2]
# 1: [0, 2]
# 2: [0, 1, 3]
# 3: [2]

Concept 4: Space Complexity Trade-offs (Sparse vs. Dense)

This is where the engineering trade-offs begin. The choice between a matrix and a list is primarily driven by the density of the graph.

Technical Explanation

• Adjacency Matrix: The space complexity is always $O(V^2)$, where $V$ is the number of vertices. You need to store a value for every possible pair of vertices, whether an edge exists or not.
• Adjacency List: The space complexity is $O(V+E)$, where $E$ is the number of edges. You store each vertex once, and each edge is represented twice in the lists (for an undirected graph).

This leads to a crucial distinction:

• Sparse Graph: A graph with very few edges. Formally, $E$ is much smaller than $V^2$ (e.g., $E$ is on the order of $V$). Social networks are typically sparse; most people are not friends with most other people. For sparse graphs, an adjacency list is far more space-efficient.
• Dense Graph: A graph with many edges, where $E$ approaches $V^2$. A graph where every city is connected to every other city would be dense. For dense graphs, the $O(V^2)$ space of the matrix is comparable to $O(V+E)$, so the space penalty is minimal.

Metaphor: The Flight Chart vs. The Contact List

If you're creating a flight chart (matrix) for every small airport in a country, but only for one tiny airline's routes, the chart will be almost entirely empty. This is a sparse graph, and you've wasted a ton of paper. A simple list of the few routes that exist (adjacency list) would be much better.

However, if you're mapping all possible flights between the 10 busiest airports in the world, the chart will be nearly full. This is a dense graph, and the chart is an efficient, quick-reference tool.

Concept 5: Time Complexity Trade-offs (Operational Performance)

The final piece of the puzzle is analyzing how fast you can perform common operations. This is often the deciding factor in an algorithm design context.

Technical Explanation

Let's compare the time complexities for the most frequent graph operations. The video below provides an excellent and detailed comparison table.

Here is a summary of the most critical trade-offs:

Note: $\text{deg}(u)$ refers to the degree of vertex u—the number of edges connected to it.

Conclusion

You've now mastered the two fundamental ways to represent a graph in memory and, more importantly, the engineering trade-offs that guide your choice. This isn't just academic; making and justifying this decision is a sign of a senior engineer.

Key Takeaways:

• Adjacency Matrix: Best for dense graphs. Its killer feature is the $O(1)$ edge existence check. Its main drawback is the rigid $O(V^2)$ space requirement.
• Adjacency List: Best for sparse graphs, which are far more common in the real world. Its killer feature is efficient $O(\text{deg}(u))$ neighbor iteration and its flexible $O(V+E)$ space usage.
• The Right Answer: In an interview, the best representation "depends on the problem." Your job is to analyze the graph's expected density and the frequency of operations (edge checks vs. neighbor traversals) to make an informed decision. For most interview problems, the adjacency list is the default choice unless a compelling reason exists to use a matrix.

Preview of the Next Lesson:
With our representations in hand, we are ready to start exploring the graph. Our next lesson will cover our first major traversal algorithm: Breadth-First Search (BFS). You'll learn how to implement BFS to systematically explore a graph level by level, a technique that is the key to finding the shortest path in unweighted graphs.