NIELIT 2017 July Scientist B (IT) - Section B: 2

Question

Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?

• A. In adjacency list representation, space is saved for sparse graphs.
• B. Deleting a vertex in adjacency list representation is easier than adjacency matrix representation.
• C. Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
• D. All of the option.

Answer 1

Answer D

A:  True , Might save a lot of memory if the graph is sparse.

B:  True, In order to delete  a vertex in  adjacency list, we need to search for the vertex which will require O(|V|) time in worst case, after this we need to traverse the edges and in worst case it will require O(|E|) time.Hence, total time complexity is O(|V|+|E|) whereas removing a vertex in adjacency matrix will require O(V$^{2}$)

C :  True , There are two pointers in adjacency list first points to the front node and the other points to the rear node.Thus insertion of a vertex can be done directly in O(1) time whereas in matrix it will require O(V$^{2}$)

Answer 2

Option D is right

(A) is trivial

(B) and (C) we have to change the dimension of the matrix which takes O(v^2) in case of Adj Matrix  => so these operations are More easier in case of Adj List

Answer 3

Comparison between Adjacency List and Adjacency Matrix representation of Graph - GeeksforGeeks