Question

Which of the following statements are correct?
• [A.] An adjacency matrix uses \(O(n^2)\) of the adjacency list is \(O(n + m)\)
• [B.] The adjacency matrix requires \(O(n^2)\) memory
• [C.] In an undirected graph, the sum of lengths of adjacency lists is \(2m\)
• [D.] The memory requirement of adjacency list is dependent on the number of edges in the graph
Choose the correct answer from the options given below:

• A. A, B, C only
• B. B, C only
• C. A, B, D only
• D. A, B, C, D

Hint:

Adjacency matrix → dense graphs, Adjacency list → sparse graphs.

Answer 1

The Correct Option is D