175 views

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

c) an incidence matrix?

edited | 175 views
+2
a) n+m

b) n*n

c) n*m
+1
0
$\Theta ( n+m)$ but please explain
+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
@Tesla,Can you please work out each option step by step by taking a simple graph?
0
@Tesla,or a complete graph as well?It will work too. :).
0
0

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

0
@Tesla,@Srestha both of you Thanks!!!

+1 vote

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

by Boss
selected
0
minimum number of edges we calculate  sparse graph

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
0

srestha what you said was right i interpreted wrong

+1
If number of edges are of same order that of vertices then sparse graph if order of numbers of edges is way more than that of vertices then dense graph
0
can someone explain what is incidence graph

+1 vote