Graph in JAVA

which is the better way to declare graphs in java ?? why??

  1. HashMap<Integer, HashSet> graph = new HashMap<> (n);
    or
  2. HashMap<Integer, ArrayList> graph = new HashMap<>(n);

Please help!!

2 Likes

I can tag some people.
@mnithinkk @aman_robotics

1 Like

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[][].

2 Likes

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.

  1. 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.

  2. 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.

  3. 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.

  4. In-case if you want to search if x adjacent to y, then case 1 is better.

  5. 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)

  6. 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.

  • If you have doubt’s about what I mean as “recreation”, then read about fill-factor in collections.

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.

2 Likes

Thanks bro, I got your point,
amazing explanation… thankyou very much :+1:

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<>();

1 Like

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.

1 Like

ok thanks bro :+1:

thanks bro :+1: