148 views

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

c) an incidence matrix?

edited | 148 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 (18.1k points)
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
1
2