For a sparse graph (E much smaller than V²), which representation is preferred?
Options
- Adjacency matrix
- Adjacency list (Correct option)
- Edge-weight matrix
- Incidence matrix
Answer
Adjacency list
Why
An adjacency list stores, for each node, only the list of its actual neighbors: O(V + E) memory. In Python: {"A": ["B", "C"], ...}.
An adjacency matrix is a V × V grid of yes/no, which wastes memory when most pairs are not connected, but checks 'is A connected to B?' in O(1).
Most real graphs (social networks, roads) are sparse.
Remember
Sparse graph → adjacency list.