Problem 1. Graph Representation Suppose a directed graph has a million nodes, mo

Question

Problem 1. Graph Representation Suppose a directed graph has a million nodes, most nodes have only a few edges, but a few nodes have hundreds of thousands of edges. In what way(s) would an adjacency-matrix representation of this graph lead to inefficiencies? In what way(s) would an adjacency-list representation of this graph lead to inefficiencies? . Design a representation for this sort of graph that avoids all the inefficiences in your answers to parts (a) and (b) Describe at least one situation (something being represented by a graph) where this sort of "unbal- anced" graph might arise.

Explanation / Answer

Solution:

a)

Since there are millions of nodes in the graph, this means that the adjacency matrix will have millions X millions size of the matrix where since some of the nodes have very few edges soo here this will be a wastage of memory and lead to inefficiency.

b)

In case of adjacency list representation, the issue is with the nodes which have hundreds of thousands of edges associated with it, this means that these nodes will have hundreds of thousands of nodes in the linked list representation of the edges and the searching time of an edge will increase here which is an inefficiency.

c)

So if the representation is done in such a way that that only important information is displayed to show. and wastage can be avoided.

so if we use incidence matrix representation then the inefficiencies can be avoided to some extent.

d)

suppose a graph is there which is like a tree and one vertex is connected to all the vertices and all the others are pendant vertices.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.