0

I am new to graph theory. I have come across many ways that state implementation of adjacency list representation of a graph in java, which includes:

ArrayList<T>[]
LinkedList<T>[]
ArrayList<ArrayList<T>>
ArrayList<HashSet<T>>
HashMap<Integer, List<T>>
etc.

I want to know which is the best data structure to use for obtaining best time complexity if I require minimum these operations on the graph:

  1. Find if two nodes are connected by an edge.
  2. Iterate over all neighbors of particular vertex.
  3. (Optional) Order all neighbors of a vertex by weight, or maybe like a priority queue.

Can you please guide as which standard library data structure is best for adjacency list implementation of graph in java to get optimum space and time complexity? (time complexity has more priority than space complexity)

Parth Prajapati
  • 17
  • 5
  • 2
    what about a `double[][]`? It is the most basic one. I would suggest you start playing around with them and see what kind of loops you need and then read up on how arrays, lists, maps and sets access their members. – luk2302 Oct 01 '17 at 17:22
  • I've already used the adjacency matrix representation arr[][] but finding neighbors takes up too much time as I have to check each vertex if it is neighbor of given vertex or not. Also, I've had some experience of standard library data structures, I'm just new to graph theory. – Parth Prajapati Oct 01 '17 at 18:21

2 Answers2

0

Keeping it simple, create a Node class that contains a TreeMap that holds references to the nodes it's connected to.

  1. Finding out if two nodes are connected is simply picking a node and querying the map O(log(n)).
  2. Iterating over all the neighbors is walking the map O(n).
  3. TreeMap does natural ordering, so pick your value and have the comparator use that value for your ordering.

Based on the information you provided anyway.

Xyrus
  • 34
  • 4
0

I would say LinkedHashSet<LinkedHashSet<T>>. This is because:

  1. Find if two nodes are connected by an edge: one call to contains() method of the inner set solve this, time required O(1)
  2. Iterate over all neighbors of particular vertex: subsequent calls to iterator.next(), each one costs O(1)
  3. Order all neighbors of a vertex by weight, or maybe like a priority queue: if you need this, change your inner implementatin to TreeSet<T> and implement the Comparable interface on your node class. TreeSet grants you that all operations will be executed in O(log n), but all your items will be sorted.

Source: Java Generics and Collections

Luca Negrini
  • 490
  • 4
  • 11
  • Nice idea using LinkedHashSet! I was unaware of its performance benefits over HashSet and TreeSet. Comparision: https://stackoverflow.com/a/42269345/6182285 – Parth Prajapati Oct 01 '17 at 18:39
  • The only downside of it is the absensce of a built in sorting capability, but it's a pretty wonderful structure. Cosider accepting the answer if this solved the problem – Luca Negrini Oct 01 '17 at 18:44
  • I'd like to wait bit more if someone comes up with better answer. If not I think your answer sums up my problem quite well. – Parth Prajapati Oct 01 '17 at 18:49