Questions
8 of 59
Which representation is better for Sparse vs Dense graphs?
Difficulty: 2/10
Graph Representation Selection
For sparse graphs, an adjacency list is generally better because the number of edges is much smaller than V², so storing only existing edges saves memory. For dense graphs, an adjacency matrix can be appropriate because most possible edges exist and O(1) edge lookup can be valuable.
javascript
- 1
Sparse graph: Prefer adjacency list.
- 2
Dense graph: Matrix can be attractive.
- 3
Need O(1) edge lookup: Matrix is advantageous.
- 4
Need efficient neighbor traversal: List is usually advantageous.
Follow-up Questions
- What representation would you use for a social network?
- Why is a matrix expensive for sparse graphs?