b) n*n

c) n*m

The Gateway to Computer Science Excellence

0 votes

*How much storage is needed to represent a simple graph with n vertices and m edges using*.

a) adjacency lists?

b) an adjacency matrix?

c) an incidence matrix?

+1

It is like chaining with hashing first we create n list corresponds to n nodes and for every outgoing edge we attach a list to that particular edge from where it is going out

0

For Adjacency List and Adjacency matrix refer the following link

https://www.geeksforgeeks.org/graph-and-its-representations/

+1 vote

Best answer

How much storage is needed to represent a simple graph with n vertices and m edges using.

Here one thing is not mentioned which is graph is directed or undirected graph

For directed Graph (n= vertices, m=edges)

1) O(m+n) for a dense graph m>> n, m$\simeq n^{2}$ thus O(n$^{2}$)

2) O(n*n) = O(n$^{2}$)

3) O(m*n) for dense graph m$\simeq n^{2}$ O(n$^{3}$)

For undirected graph (n= vertices, m=edges)

1) O(n+2*m) for a dense graph m>> n, m$\simeq n^{2}$ thus O(n$^{2}$)

2) O(n*n) = O(n$^{2}$)

3) O(m*n) for dense graph m$\simeq n^{2}$ O(n$^{3}$)

Space complexity wise it doesn't make any difference in directed vs undirected but if we go for deeper analysis extra cost is associated with each method

0

minimum number of edges we calculate sparse graph

and for maximum number of edges we calculate dense graph , right?

and for maximum number of edges we calculate dense graph , right?

0

for minimum number of edges we use adjacency lists and

for maximum number of edges we use adjacency matrix

for maximum number of edges we use adjacency matrix

52,218 questions

59,890 answers

201,084 comments

118,128 users