Graph Data Structure: Adjacency List and Matrix

Key Insights

Adjacency matrices excel at O(1) edge lookups but waste memory on sparse graphs with O(V²) space complexity, making them ideal for dense graphs where edges exceed V²/2
Adjacency lists use O(V + E) space and provide O(degree) neighbor iteration, making them the default choice for most real-world graphs which tend to be sparse
Your choice of representation directly impacts algorithm performance—BFS on an adjacency list runs in O(V + E) while the same algorithm on a matrix runs in O(V²)

Introduction to Graphs

Graphs are everywhere in software engineering: social networks, routing systems, dependency resolution, recommendation engines. Before diving into implementation, let’s establish the terminology.

A graph consists of vertices (nodes) and edges (connections between nodes). Edges can be directed (one-way) or undirected (bidirectional). They can also be weighted (carrying a cost or distance) or unweighted.

The representation you choose for your graph isn’t just an implementation detail—it fundamentally affects your application’s performance. A social network with millions of users but only hundreds of connections per user behaves very differently from a small network where everyone knows everyone. Choose wrong, and you’ll either waste gigabytes of memory or turn O(1) operations into O(V) crawls.

Adjacency Matrix Representation

An adjacency matrix represents a graph as a 2D array where matrix[i][j] indicates whether an edge exists from vertex i to vertex j. For unweighted graphs, this is typically a boolean or 0/1. For weighted graphs, store the weight directly (using a sentinel value like infinity for non-edges).

The space complexity is always O(V²), regardless of how many edges exist. This is the matrix’s fundamental trade-off: you pay for every possible edge whether it exists or not.

class AdjacencyMatrix:
    def __init__(self, num_vertices: int):
        self.num_vertices = num_vertices
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
    
    def add_edge(self, src: int, dest: int, weight: int = 1) -> None:
        """Add an edge from src to dest. For undirected graphs, call twice."""
        if not self._valid_vertex(src) or not self._valid_vertex(dest):
            raise ValueError("Invalid vertex index")
        self.matrix[src][dest] = weight
    
    def remove_edge(self, src: int, dest: int) -> None:
        """Remove the edge from src to dest."""
        if not self._valid_vertex(src) or not self._valid_vertex(dest):
            raise ValueError("Invalid vertex index")
        self.matrix[src][dest] = 0
    
    def has_edge(self, src: int, dest: int) -> bool:
        """Check if an edge exists from src to dest. O(1) operation."""
        if not self._valid_vertex(src) or not self._valid_vertex(dest):
            return False
        return self.matrix[src][dest] != 0
    
    def get_neighbors(self, vertex: int) -> list[int]:
        """Return all vertices adjacent to the given vertex. O(V) operation."""
        if not self._valid_vertex(vertex):
            raise ValueError("Invalid vertex index")
        return [i for i in range(self.num_vertices) if self.matrix[vertex][i] != 0]
    
    def _valid_vertex(self, v: int) -> bool:
        return 0 <= v < self.num_vertices

Notice that has_edge is O(1)—just an array lookup. But get_neighbors must scan the entire row, making it O(V) regardless of how many neighbors actually exist. This becomes painful when you need to traverse the graph.

Adjacency List Representation

An adjacency list stores only the edges that exist. Each vertex maintains a list of its neighbors. The space complexity is O(V + E)—you pay for vertices plus actual edges, not potential edges.

from collections import defaultdict
from typing import NamedTuple

class Edge(NamedTuple):
    dest: int
    weight: int = 1

class AdjacencyList:
    def __init__(self):
        self.graph: dict[int, list[Edge]] = defaultdict(list)
        self._vertices: set[int] = set()
    
    def add_vertex(self, vertex: int) -> None:
        """Explicitly add a vertex (useful for isolated vertices)."""
        self._vertices.add(vertex)
    
    def add_edge(self, src: int, dest: int, weight: int = 1) -> None:
        """Add an edge from src to dest. For undirected graphs, call twice."""
        self._vertices.add(src)
        self._vertices.add(dest)
        self.graph[src].append(Edge(dest, weight))
    
    def remove_edge(self, src: int, dest: int) -> None:
        """Remove the edge from src to dest. O(degree) operation."""
        self.graph[src] = [e for e in self.graph[src] if e.dest != dest]
    
    def has_edge(self, src: int, dest: int) -> bool:
        """Check if an edge exists. O(degree) operation."""
        return any(e.dest == dest for e in self.graph[src])
    
    def get_neighbors(self, vertex: int) -> list[int]:
        """Return all vertices adjacent to the given vertex. O(degree) operation."""
        return [e.dest for e in self.graph[vertex]]
    
    def get_weighted_neighbors(self, vertex: int) -> list[Edge]:
        """Return neighbors with their edge weights."""
        return list(self.graph[vertex])
    
    @property
    def num_vertices(self) -> int:
        return len(self._vertices)

The key difference: get_neighbors now returns in O(degree) time—proportional to actual neighbors, not total vertices. For a social network where users average 200 friends out of millions, this is the difference between 200 operations and millions.

However, has_edge is now O(degree) instead of O(1). You’re trading lookup speed for memory efficiency and iteration speed.

Performance Comparison

Let’s quantify the differences:

Operation	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Add Edge	O(1)	O(1)
Remove Edge	O(1)	O(degree)
Check Edge Exists	O(1)	O(degree)
Get All Neighbors	O(V)	O(degree)
Iterate All Edges	O(V²)	O(V + E)

Here’s a benchmark demonstrating the practical impact:

import time
import random

def benchmark_neighbor_iteration(num_vertices: int, edge_probability: float):
    """Compare neighbor iteration performance."""
    
    # Build both representations with same random graph
    matrix = AdjacencyMatrix(num_vertices)
    adj_list = AdjacencyList()
    
    edges_added = 0
    for i in range(num_vertices):
        adj_list.add_vertex(i)
        for j in range(num_vertices):
            if random.random() < edge_probability:
                matrix.add_edge(i, j)
                adj_list.add_edge(i, j)
                edges_added += 1
    
    print(f"Graph: {num_vertices} vertices, {edges_added} edges")
    print(f"Density: {edges_added / (num_vertices * num_vertices):.2%}")
    
    # Benchmark: iterate all neighbors of all vertices
    start = time.perf_counter()
    for v in range(num_vertices):
        neighbors = matrix.get_neighbors(v)
        _ = len(neighbors)  # Force evaluation
    matrix_time = time.perf_counter() - start
    
    start = time.perf_counter()
    for v in range(num_vertices):
        neighbors = adj_list.get_neighbors(v)
        _ = len(neighbors)
    list_time = time.perf_counter() - start
    
    print(f"Matrix neighbor iteration: {matrix_time:.4f}s")
    print(f"List neighbor iteration: {list_time:.4f}s")
    print(f"List is {matrix_time / list_time:.1f}x faster\n")

# Sparse graph (typical real-world scenario)
benchmark_neighbor_iteration(1000, 0.01)

# Dense graph
benchmark_neighbor_iteration(1000, 0.5)

Running this reveals the pattern: for sparse graphs, adjacency lists dominate. As density approaches 50% or higher, the matrix’s O(1) edge checks start to matter more, especially if your algorithm performs many existence checks.

When to Use Each Representation

Use an adjacency matrix when:

Your graph is dense (edges > V²/4)
You need frequent O(1) edge existence checks
Vertex count is small and fixed (under ~10,000 vertices)
You’re implementing algorithms like Floyd-Warshall that naturally operate on matrices
Memory isn’t a constraint

Use an adjacency list when:

Your graph is sparse (most real-world graphs)
You frequently iterate over neighbors (BFS, DFS, Dijkstra)
Vertex count is large or dynamic
Memory efficiency matters
You need to store edge metadata beyond simple weights

The vast majority of practical applications should default to adjacency lists. Social graphs, road networks, dependency graphs, and web link structures are all sparse. A city’s road network might have millions of intersections but each intersection connects to only 3-4 roads.

Practical Implementation: BFS Traversal

Let’s see how representation affects a real algorithm. BFS visits all reachable vertices level by level—the foundation for shortest path in unweighted graphs.

from collections import deque

def bfs_matrix(graph: AdjacencyMatrix, start: int) -> list[int]:
    """BFS traversal using adjacency matrix. O(V²) time complexity."""
    visited = [False] * graph.num_vertices
    order = []
    queue = deque([start])
    visited[start] = True
    
    while queue:
        vertex = queue.popleft()
        order.append(vertex)
        
        # This loop runs V times per vertex = O(V²) total
        for neighbor in graph.get_neighbors(vertex):
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
    
    return order

def bfs_list(graph: AdjacencyList, start: int) -> list[int]:
    """BFS traversal using adjacency list. O(V + E) time complexity."""
    visited = set()
    order = []
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        order.append(vertex)
        
        # This loop runs degree(vertex) times = O(E) total across all vertices
        for neighbor in graph.get_neighbors(vertex):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return order

The algorithms look nearly identical, but their performance characteristics differ dramatically. With the matrix, get_neighbors scans V elements for every vertex we visit, giving O(V²) total. With the list, we only examine actual edges, giving O(V + E).

For a sparse graph with 100,000 vertices and 500,000 edges, the matrix version performs 10 billion operations while the list version performs 600,000. That’s a 16,000x difference.

Conclusion

Graph representation isn’t a decision to make lightly. The wrong choice can turn a linear algorithm into a quadratic one or waste gigabytes of memory storing zeros.

Default to adjacency lists. Most graphs you’ll encounter are sparse, and most graph algorithms spend their time iterating neighbors. The O(V + E) space and O(degree) neighbor access make lists the practical choice.

Reach for adjacency matrices when you have small, dense graphs or algorithms that hammer edge existence checks. Matrix multiplication-based algorithms and some dynamic programming approaches also naturally fit the matrix representation.

When in doubt, profile with realistic data. A graph with 1,000 vertices behaves very differently from one with 1,000,000, and theoretical complexity only tells part of the story.