-1

I am new to graph data structure. Everywhere on google it is said to be list(or array ) of linked list. My question is can not it be represented as list of list(in java array list of array list) or map of list(in java HashMap with key as node and value as array list of connected node ) ?

In all three mentioned approach I see time complexity

To find if two nodes are connected - O(v) To find all connected nodes - O(v)

Also space complexity will also be more or less same .

So why Adjacency List is said to be list(or array ) of linked list not as list of list or map of list ?

0

A list of list or a map of list or a map of map are just fine for implementing an adjacency list. No real downside to any of them. I personally use a list of lists in Java whenever I need an unweighted graph and a list of hashmaps if I need a weighted one.

As for why Adjacency list is said to be array of linked lists, I haven't really seen this claimed as a golden standard anywhere. The wiki article mentions three common implementations and it includes both linked lists and dynamic arrays.

0

A List of List will be dynamic(in terms of number of Vertices) in nature and hence can be costly in terms of reallocation(as the default size of ArrayList in JAVA is 10). Since we already know the size of a graph while constructing it. So it is better to use an array of List rather than using a List of List or a Map of List. You can read more about the List in JAVA here.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.