Graph Representation: Adjacency List

Math for CS · Axiom Academy

The go-to representation for sparse graphs This is the most common graph representation in practice. Nearly every textbook algorithm (BFS, DFS, Dijkstra, Kruskal) is written for adjacency lists. Consider a graph with 5 vertices and edges . For undirected graphs, each edge appears twice — once in each endpoint's list. For directed graphs, edge appears only in u 's list. In most languages, an adjacency list is an array of dynamic arrays (or linked lists). For weighted graphs, store tuples (neighbor, weight) instead of just neighbors. We store n list headers plus 2m entries total (each undirected edge contributes to two lists). For sparse graphs where m = O(n) , this is O(n) — dramatically better than the O(n^2) of an adjacency matrix. Adjacency matrix: 10^ 12 entries (1 trillion) — about 1 TB of memory Adjacency list: entries — about 1.6 GB of memory When to Use Each Representation The graph is sparse ( ) — most real-world graphs You run BFS/DFS or other traversals that iterate over neighbors Memory is a concern (large n ) You need constant-time edge lookup You use matrix algebra (powers, spectral methods, Floyd-Warshall) Replace each neighbor list with a hash set. Now edge lookup is O(1) expected time while keeping O(n + m) space. This gives the best of both worlds for many applications. A simple list of all edges (u, v, w) . Uses O(m) space. Fast to iterate all edges but slow for neighbor queries. Used by Kruskal's algorithm (sort edges by weight).

This is the written version of the interactive lesson above. See the full Math for CS course.