Advantages of map representation over array representation of adjacency list

#1

please give in detail the advantages of map implementation of adj list over its array implementation?

#2

@Rj.25
Hello Reechika,
To find all neighbours of any node you need to traverse complete row of adjacency matrix due to which time complexity (O(total number of nodes in graph) ) is more (specially when u have sparse matrix i.e matrix with less entry) but to find same thing in adjacency list is easy and less time consuming(basically o(no of neighbours)

example consider a row of adajcancy matrix (total 10 nodes in graph)

row
1 [0,0,0,0,0,0,0,0,1,0]

now ajacency list for same will look like
1->9 (i.e 9 is neighbour)
clearly we can see adjacency list is efficient than adjacency matrix

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

sir thanku for answering but would it be ok if in addition u tell me about the advantages of hashmap implementation of adjacency list representation over array implementation of adjacency list representation?

#5

Hello @Rj.25,

The advantage depends upon the way you are storing the edges.
You might not always wants to represent a vertex with an integer i.e. the index of the array.
Hashmap would be a better choice for such cases when you wants to represent a node with a complex structure or datatype like strings.

Hope, this would help.
Give a like if you are satisfied.

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#8

@Rj.25 use string iterator then.

#9

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.