Question

Comparing the space needed to store a directed graph using an adjacency matrix vs an adjacency list. Which ones of the following are TRUE? Choose all that apply.

Note: All comparisons are based on the asymptotic bound on the space complexity, i.e., we ignore constant factors and lower-order terms.
A. If the graph is very dense, then adjacency matrix uses less space than adjacency list.
B. If the graph is very sparse, then adjacency matrix uses less space than adjacency list.
C. If the graph is very sparse, then adjacency list uses less space than adjacency matrix.
D. If the graph is very dense, then adjacency list uses less space than adjacency matrix.

Answer 1

In comparing storage methods for directed graphs, an adjacency matrix is more space-efficient for dense graphs, while an adjacency list is better for sparse graphs. A dense graph means an adjacency matrix uses less space, whereas a sparse graph means an adjacency list uses less space.

Step-by-step explanation:

When determining the most efficient way to store a directed graph in terms of space, one might compare the use of an adjacency matrix versus an adjacency list. The choice between these two methods depends on the properties of the graph, particularly its density.

Adjacency matrices require a space that is proportional to the square of the number of vertices (V^2), so they are efficient for dense graphs where the number of edges (E) is close to V^2. On the other hand, adjacency lists require space proportional to the number of vertices plus the number of edges (V + E), which makes them more space-efficient for sparse graphs where E is much less than V^2.

Option A (TRUE): If the graph is very dense, then adjacency matrix uses less space than adjacency list.

Option B (FALSE): If the graph is very sparse, then adjacency matrix uses more space than adjacency list.

Option C (TRUE): If the graph is very sparse, then adjacency list uses less space than adjacency matrix.

Option D (FALSE): If the graph is very dense, then adjacency matrix uses more space due to storing all possible connections, whereas adjacency list would be inefficient as it would have to list nearly every edge for every vertex.