For some sparse graph an adjacency list is more space efficient against an adjacency matrix.Group of answer choicesTrueFalse

Answer: True

When dealing with sparse graphs, an adjacency list is generally more space-efficient compared to an adjacency matrix. Here’s why:

1. Definition of Sparse Graphs: A sparse graph is one where the number of edges is much less than the maximum possible number of edges. For an undirected graph with $n$ vertices, the maximum number of edges is $\frac{n(n-1)}{2}$.

2. Space Usage:

   • Adjacency Matrix: An adjacency matrix for a graph with $n$ vertices requires $n^2$ space, regardless of the number of edges. This means for sparse graphs, the matrix will contain a lot of zeros, representing the absence of edges.
   • Adjacency List: An adjacency list, on the other hand, requires space proportional to the number of vertices plus the number of edges, or $O(n + e)$, where $e$ is the number of edges. This efficient use of space is particularly beneficial in sparse graphs.

3. Conclusion: Because the adjacency list only stores edges that are present instead of allocating space for all possible edges, it is more space-efficient than the adjacency matrix for sparse graphs.

Final Answer

True: An adjacency list is more space-efficient than an adjacency matrix for sparse graphs.