The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
148 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 (35.2k points)
edited by | 148 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 (18.1k points)
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

Related questions

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
50,362 questions
55,786 answers
192,411 comments
90,919 users