Data Structures and Algorithms
Which is an appropriate way to store in memory a sparse graph, one with few edges compared with its number of vertices, such as a road network with about 1 million vertices and 3 million edges?
- AAn adjacency matrix: it can check whether two vertices are connected in O(1) and also uses the least memory
- BAdjacency lists: memory is proportional to the number of vertices plus the number of edges, and they suit following the edges out of a vertex one by one
- CAn adjacency matrix: its memory is proportional only to the number of edges
Show answer and explanation
Answer: B. Adjacency lists: memory is proportional to the number of vertices plus the number of edges, and they suit following the edges out of a vertex one by one
An adjacency matrix uses a V × V table for V vertices, so 1 million vertices need 10¹² entries, about 125 GB even at 1 bit per entry. Adjacency lists store only the neighbors of each vertex, so memory is O(V + E), only a few million entries in this example. An adjacency matrix has the advantage of checking for an edge in O(1) and suits dense graphs or graphs with few vertices. For processing that follows the edges out of each vertex in turn, such as breadth-first search and Dijkstra's algorithm, adjacency lists are more efficient.
- A. Checking for an edge in O(1) is true, but the memory grows with the square of the number of vertices, which is very wasteful for a sparse graph.
- B. Correct. Memory is only O(V + E), and they suit processing that walks through neighboring vertices.
- C. The size of an adjacency matrix does not depend on the number of edges; it is the square of the number of vertices.