VI · Graphs & sets
Adjacency list
Each node, its neighbours.
The story
For sparse graphs (most real graphs), a list of edges per vertex beats a |V|² matrix. Storage is O(V+E) rather than O(V²); iteration over neighbours is O(degree). Used everywhere except dense academic problem sets.
How it works
An array indexed by vertex. Each entry is a list (vector or linked list) of (neighbour, weight) pairs. For directed graphs, each edge appears once; undirected, twice.
Where it lives
Every BFS and DFS. Web crawlers. Social network graphs. Linux's scheduler dependency tracker. NetworkX, igraph, Boost Graph Library — everything.
The key insight
For graphs with E ≪ V², adjacency list is always better. The exception: dense graphs (E ≈ V²) where the matrix's O(1) edge check dominates list scans.