Representation Trade-offs for Common Operations
What you'll learn: How different graph representations excel at different operations, helping you choose the right one for your use case.
When working with graphs, you'll perform three common operations repeatedly: checking if an edge exists between two vertices, finding all neighbors of a vertex, and iterating over all edges. Each representation—adjacency matrix, adjacency list, and edge list—handles these differently.
Edge Existence Check
Adjacency Matrix shines here: checking if vertex u connects to vertex v is just matrix[u][v], an O(1) lookup. Adjacency List must scan through u's neighbor list, taking O(degree) time in the worst case. Edge List is slowest, requiring a scan of all edges: O(E).
Finding All Neighbors
Adjacency List wins decisively: all neighbors are stored together, so you access them in O(degree) time—optimal since you must visit each neighbor anyway. Adjacency Matrix forces you to scan an entire row of V entries, even if most are zeros: O(V). Edge List again requires scanning all edges: O(E).
Iterating Over All Edges
Edge List is purpose-built for this: O(E) time, one pass through. Adjacency List also achieves O(E) by visiting each list once. Adjacency Matrix must check all V² cells, finding only E edges among them: O(V²).
Choosing Wisely
Think of it like organizing contacts: a matrix is like a grid where you instantly locate anyone but waste space on empty cells. A list is like categorized folders—great for "who are Bob's friends?" but slower for "are Alice and Carol connected?" An edge list is like a simple timeline of all connections.
Key Takeaway: Adjacency matrices excel at edge existence checks (O(1)) but waste space; adjacency lists optimize neighbor finding and are space-efficient for sparse graphs; edge lists are simplest for iterating all edges but slow for targeted queries.