which is the better way to declare graphs in java ?? why??
- HashMap<Integer, HashSet> graph = new HashMap<> (n);
or - HashMap<Integer, ArrayList> graph = new HashMap<>(n);
Please help!!
which is the better way to declare graphs in java ?? why??
Please help!!
If you are storing as an adjacency list, you can use ArrayList<Integer>[]
, and if you are storing as an adjacency matrix, you can use int[][]
.
I think its depend upon requirements such as if you are solving problem where you want to repeatedly check whether vertex X is linked to Vertex Y or not in that case i refer to HashSet
Depends on your use-case,
I think you are trying to store adjacency list here.
Letâs assume, For building the adjacency list by parsing the I/P, both of them will take O(n) for Directed graph and O(2n) for undirected graph.
But since you already passed ânâ as constructor parameter of HashMap, there wonât be recreation after fill-factor is breached. But the internal HashSet/Arraylist in both cases will have the fill-factor breached which makes the recreation of HashSet/Arraylist.
The major similarity between two is, if you have use-case that you want to iterate over all the adjacencies, they both behaves the same.
In-case if you want to search if x adjacent to y, then case 1 is better.
In-case if you want to search if x adjacent to y, if yâs index is known somehow with respect to x, then case 2 is better (which would be a rare case)
For all the above, Better use
HashMap<Integer, Queue> graph = new HashMap<>(n);
where,in initialize Queue as
Queue queue = new LinkedList<>();
Because linkedlist is better for insertion/deletion at the end which will always happen in O(1) and recreation doesnât happen afaik.
Heads-up : When you create a new ArrayList itâs default capacity is only 10. But after you insert 10 elements and when you try to insert 11th element, a new arraylist is created with better size, and all 10 elements are copied to new arraylist.
Thanks bro, I got your point,
amazing explanation⌠thankyou very much
but bro ⌠if we use Queue, then to get the adjacent vertices of any vertex we will have to keep removing the elements in the head of queue so as to access next elements⌠and in this way we might end up loosing all elements and next time if we again want to access the adjacent neighbours we will have an empty queue. @mnithinkk
No bro. You will not lose all elements on removing head single time.
Queue (Assuming you wonât provide Priority queue implementation) concept is based on offer() and poll()
offer() keeps adding element in the end.
poll() keeps removing the head and makes (head+1) as next head.
Queue queue = new LinkedList<>();
Itâs better to use HashMap<Integer, ArrayList> graph = new HashMap<>(n); because some mapping can be repeative. if you used HashSet then you will not get proper mapping.
ok thanks bro
thanks bro