JEST Sample Question-5

Question

Describe two different data structures to represent a graph. For each such representation, specify a simple property about the graph that can be more efficiently checked in that representation than in the other representation. Indicate the worst case time required for verifying both of your properties in either representation.

Answer 1

Graphs can be represented in two ways :-

1. Adjacency Matrix.

2. Adjacency List.

Edge existential property can be checked in $\Theta(1)$ time using Adjacency Matrix representation , but using adjacency list it has a worst case complexity of $O(deg(v))$ , deg(v) in worst case is n-1 , thus in worst case using adjacency list would take $O(n)$.

Counting total number of edges can be done using adjacency list in a more effective manner with TC of $O(V)$ , but with Adjacency Matrix it would take $O(v^{2})$