Question

Analysis Study Case Question:

• Suppose that your computer only has enough memory to store 40000 entries. Which best graph data structure(s) – you can choose more than 1 -- should you use to store a simple undirected graph with 200 vertices, 19900 edges, and the existence of edge(u,v) is frequently asked?

–Adjacency Matrix

–Adjacency List

–Edge List

Answer 1

The adjacency list nad adjacency matrix can be used in the above-mentioned case. If the above graph is represented using the adjacency matrix then that would occupy the O(n^2) space where n representing the number of vertices. But if we use this to represent in the form of adjacency list then that would use less space compared to the adjacency matrix and then the unused places in the adjacency matrix where there is no edge present b/w two vertices won't be mentioned in the adjacency list.The edge list concept can not be used here since the number of efges is very high so it will require O(E) time to make the graph where E reprents the number of edges and further more time will be required to search to find the time in the graph to check for the existence of edge.

but in the above question it is also mentioned to know the the existence of edge(u,v) so finding if an edge between two vertices is present in adjacency list will consume a lot of time. If the list are appended in the sorted form using some method like set or map then in that case an extra O(log n) time would be consumed where n represents the length of the number of edges connected to a respective node. So we can use the adjacency list form but here we will have to keep in mind to store the data in sorted form for every node of the graph so that less time is used to search to find the existence of the edge.

Since here the number of vertices is very less so it is advisable to store it in the form of adjacency matrix so that the existence of edge(u,v) can be computed in the O(1) time and also it is also more simple and easy to understand in the above mentioned case.

So for the above case adjacency matrix is simpler and easily understandable approach apart form this adjacency list might also be used but you need to be extra careful to consume less time while checking the existence of edge(u,v). But edge list concept should not be used for the above case.