Algorithms and Data Structures · Junior · Question 57 of 75
How is a graph usually stored when it has many vertices but few edges?
- 1As an n × n matrix filled with zeros and ones
- 2As one sorted array containing all the vertices
- ✓Correct answer: As an adjacency list: each vertex with its neighbors
Explanation
An adjacency list takes O(V + E) memory, while a matrix always takes O(V²), which is wasteful for sparse graphs. The matrix is handy when the graph is dense or you need an O(1) "is there an edge?" check.