Questions: Graph Representations: Adjacency List vs. Adjacency Matrix

Question 1

You are implementing BFS on a social network graph with 1 million users (V = 10⁶) and 10 million friendships (E = 10⁷). Which representation gives better BFS performance, and why?

• A. Adjacency matrix — O(1) edge lookup makes the traversal faster at each step
• B. Adjacency list — O(V + E) traversal avoids scanning empty matrix rows for sparse graphs
• C. Either is equivalent — BFS visits every edge once regardless of representation
• D. Adjacency matrix — it uses less memory since it is stored as a fixed-size array

Answer: (B)

BFS examines every vertex and every edge once. With an adjacency list, this costs O(V + E) = O(10⁶ + 10⁷) ≈ O(10⁷). With an adjacency matrix, you must scan every row to find neighbors, even rows with few or no edges — that costs O(V²) = O(10¹²). The graph here is very sparse (E/V = 10, far below V = 10⁶), so the matrix wastes enormous work scanning empty entries. Option A is wrong because O(1) edge lookup is not the bottleneck in BFS — finding all neighbors is. Option D is wrong: the matrix would require storing 10¹² entries, vastly more than the list's O(V + E) = O(10⁷).

Question 2

What is the time complexity of checking whether a directed edge from vertex u to vertex v exists in an adjacency list representation?

• A. O(1) — array indexing gives direct access to u's neighbor list
• B. O(V) — you must scan all vertices to find v
• C. O(degree(u)) — you must scan u's neighbor list to find v
• D. O(E) — edge lookup requires scanning all edges in the worst case

Answer: (C)

In an adjacency list, you index directly into the list for vertex u in O(1), but then must scan that list to check whether v appears in it. In the worst case (v is last or absent), this scans all of u's neighbors, taking O(degree(u)). For a vertex with high degree, this can be slow. By contrast, an adjacency matrix answers the same question in O(1) by reading matrix[u][v] directly. This is the fundamental trade-off: adjacency lists are space-efficient but slow for edge queries; matrices are space-hungry but fast for edge queries.

Question 3

In an undirected graph stored as an adjacency list, each edge (u, v) is represented twice — once in u's list and once in v's list — so the total storage for edges is 2E entries.

• T. True
• F. False

Answer: True

An undirected edge (u, v) means both u connects to v and v connects to u. In an adjacency list, v appears in u's neighbor list and u appears in v's neighbor list. So each undirected edge contributes two list entries. The total space for all edges is 2E, and with the V-entry array of lists, total space is O(V + 2E) = O(V + E). In a directed graph, each edge (u → v) appears only in u's list, so total edge entries equal E exactly.

Question 4

An adjacency matrix usually uses less memory than an adjacency list because it avoids the pointer overhead of linked lists.

• T. True
• F. False

Answer: False

An adjacency matrix always uses O(V²) space regardless of how many edges exist. An adjacency list uses O(V + E) space. For sparse graphs (E ≪ V²), the adjacency list is far more compact. For example, a graph with V = 10,000 vertices and E = 50,000 edges uses a 100-million-entry matrix vs. roughly 60,000 list entries — a 1,600× difference. The matrix only uses less memory when the graph is dense enough that E is close to V², in which case O(V + E) ≈ O(V²) anyway. Pointer overhead in adjacency lists is real but small relative to the O(V²) vs. O(V + E) space difference for sparse graphs.

Question 5

Why does the choice between adjacency list and adjacency matrix affect the time complexity of BFS and DFS, not just memory usage?

Model answer: BFS and DFS must examine every edge at least once. The representation determines how efficiently that examination happens. With an adjacency list, finding all neighbors of a vertex takes time proportional to its degree — you only look at edges that actually exist. Across the whole traversal, this sums to O(V + E). With an adjacency matrix, finding all neighbors of vertex u requires scanning the entire u-th row of V entries, whether or not those edges exist. This costs O(V) per vertex, for O(V²) total. For sparse graphs, O(V + E) is much smaller than O(V²), so the representation choice changes the asymptotic complexity of the algorithm, not just the constant factor.

The key insight is that representation determines what work the algorithm must do, not just how much memory it uses. An algorithm running on an adjacency matrix 'pays' for edges that don't exist — it must check each matrix entry to determine it's 0. An adjacency list skips non-edges entirely because they simply aren't listed. This is why adjacency lists are the default: most real-world graphs are sparse, and the algorithm's work should scale with what's actually there.