For some sparse graph an adjacency list is more space efficient against an adjacency matrix.

Category: QuestionsFor some sparse graph an adjacency list is more space efficient against an adjacency matrix.
Editor">Editor Staff asked 4 weeks ago

For some sparse graph an adjacency list is more space efficient against an adjacency matrix.
 
(a) True
 
(b) False
 
Enquiry is from Adjacency List topic in portion Graph of Data Structures & Algorithms I
 
I got this question in my homework.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Right option is (a) True
 
Easiest explanation – Space complexity for adjacency matrix is always O(V*V) while space complexity for adjacency list in this case would be O(V).