On a sparse graph (E far less than V²), the adjacency list representation
Awastes O(V²) bits regardless of edge count
Buses O(V + E) space, much less than O(V²)
Cis forbidden by the SQL standard
Dsupports only undirected graphs
Answer & Solution
Correct answer: B. uses O(V + E) space, much less than O(V²)
Adjacency lists store per-vertex neighbour lists, totalling O(V + E) cells. On sparse graphs this is far smaller than the matrix's fixed O(V²). Matrices waste rows of zeros for vertices with few neighbours. Lists handle both directed and undirected graphs; SQL has nothing to do with this choice.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for