Question

Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is __________

(a) O(V)

(b) O(E*E)

(c) O(E)

(d) O(E+V)

Enquiry is from Adjacency List topic in portion Graph of Data Structures & Algorithms I

The question was posed to me at a job interview.

Answer 1

Right answer is (c) O(E)

The best explanation: In an adjacency list for every vertex there is a linked list which have the values of the edges to which it is connected.