Question

Suppose a graph has a million vertices. What would be a reason to use an adjacency matrix representation?

choose one
If the graph is sparse.
If we often wish to iterate over all neighbors of a vertex.
If the graph isn't "simple."
If there is about a 50% chance for any two vertices to be connected
None of the other reasons.

Answer 1

If the graph is sparse.

When the graph has a large number of vertices but only a small number of edges, the adjacency matrix representation can still be efficient in terms of memory and lookup times. The space complexity of an adjacency matrix is O(n^2), where n is the number of vertices. Therefore, if the graph is sparse, it means that a significant amount of memory is being wasted on representing non-existent edges in a matrix. In such cases, an adjacency list would be a better choice since it only represents actual edges, saving a lot of memory.

Step-by-step explanation: