The Gateway to Computer Science Excellence
0 votes
175 views

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?

in Graph Theory by Boss
edited by | 175 views
+2
a) n+m

b) n*n

c) n*m
+1
Shouldn't adjacency list be n+m?
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

For Adjacency List and Adjacency matrix refer the following link 

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

For incidence, list click here

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

1 Answer

+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 

by Boss
selected by
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
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,890 answers
201,084 comments
118,128 users