edited by
2,449 views
0 votes
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?

edited by

1 Answer

Best answer
1 votes
1 votes

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 

selected by

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
0 answers
2
0 votes
0 votes
1 answer
3
dd asked Nov 22, 2016
599 views
If G is a simple graph with 15 edges and $\bar G$ has 13 edges, how many vertices does G have?
1 votes
1 votes
1 answer
4
dd asked Nov 22, 2016
3,087 views
For which values of n are these graphs regular?1. $K_n$2. $C_n$3. $W_n$4. $Q_n$