retagged by
17,719 views
0 votes
0 votes

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

  1. In adjacency list representation, space is saved for sparse graphs.
  2. Deleting a vertex in adjacency list representation is easier than adjacency matrix representation.
  3. Adding a vertex in adjacency list representation is easier than adjacency matrix representation.
  4. All of the option.
retagged by

3 Answers

0 votes
0 votes

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}$)

0 votes
0 votes
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
edited by
Answer:

Related questions

0 votes
0 votes
1 answer
1
admin asked Mar 30, 2020
9,911 views
Given an undirected graph $G$ with $V$ vertices and $E$ edges, the sum of the degrees of all vertices is$E$$2E$$V$$2V$
0 votes
0 votes
1 answer
2
admin asked Mar 30, 2020
2,048 views
A path in graph $G$, which contains every vertex of $G$ and only once?Euler circuitHamiltonian pathEuler PathHamiltonian Circuit
0 votes
0 votes
1 answer
3
admin asked Mar 30, 2020
883 views
In a given following graph among the following sequences: abeghf abfehgabfhgeafghbe Which are depth first traversals of the above graph?I,II and IV onlyI and IV onlyII,II...
1 votes
1 votes
1 answer
4
admin asked Mar 30, 2020
952 views
Considering the following graph, which one of the following set of edges represents all the bridges of the given graph?$(a,b), (e,f)$$(a,b), (a,c)$$(c,d), (d,h)$$(a,b)$