graphs

Question

adding an node in adjancy matrix and adjacancy list takes _________time?

expalin

Comments

I guess it should be O(1). In the case of matrix you will need to intialize the correct row and column and in case of a list you will have to add a node in front of the corresponding list

Answer 1

Adding node in adjacancy matrix : You need O(n²) time. consider the case undirected complete graph u need to update entries on n-1 vertices ( which take O(1) to update but finding take O(n) time ) so O(n²) , one has to increase the storage for a n² matrix to (n+1)² i.e. you will have to copy the whole content of the former smaller matrix to the newly allocated memory for the bigger matrix, because the mapping won't fit anymore. And that is obviously an O(n²) operation.

consider above 3 graph and assume d in 1st graph is added .you need to change the entries of a,b,c from d and from a,b,c to d,

Adding node in adjacancy list : It will take O(n) time in worst case when graph is dense , thats why these used when graph is sparse .

Comments

Yes of course the adjacency matrix is used when the graph is dense else adjacency list is used.

Answer 2

In adding a vertex , 

a) in case of adjacency matrix , it takes O(V²) time since adding a node requires that the dimension of the matrix needs to be changed and also the fact we know that in 1 D array of n elements , insertion of a new element somewhere in the middle takes O(n) time due to shift operations.So for each row , O(V) time.So for V rows = O(V²) time

b) In case of the adjacency linked list , we just add the node hence O(1) time.

Reference : https://en.wikipedia.org/wiki/Graph_(abstract_data_type)

Here you can find the comparision of running time complexities of operations of graph for adjacency matrix , adjacency list and incidence matrix representations of graph.

Comments

2n+1 updations is enough why n2

---

Bcoz I m not saying about updations but to resize your array you need O(V) time for each row hence overall time = O(V²)