Course contentsShow
← Computer Science
Lesson 681 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Representation Trade-offs for Common Operations

Compare representations for checking edge existence, finding neighbors, and iterating over edges.

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.