Would you use the adjacency list structure or the adjacency

Would you use the adjacency list structure or the adjacency matrix structure for a graph with 10,000 vertices and 20,000 edges when it is important to use as little space as possible

a. Adjacency list

b. Adjacency Matrix

c. Both work well in this case

Solution

a) The adjacency list structure is preferable. Indeed, the adjacency matrix structure wastes a lot of space. It allocates entries for 100,000,000 edges while the graph has only 20,000 edges.

b) The adjacency matrix structure is preferable. Indeed, it supports the operation are Adjacent() in O(1) time, irrespective of the number of vertices or edges.

c) In general, both structures work well in this case. Regarding the space requirement, there is no clear winner. Note that the exact space usage of the two structures depends on the implementation details.