I want to implement (in Java) a Graph class using AdjacencyLists, I'd use this class on minimum spanning tree for Prim's Algorithm.
I read that there's many way for doing this but I can't use data structures built upon simpler primitive data types (LinkedList, stack and so on) so I thought that maybe a good solution would be using HashTable and merge them with ArrayList instead of LinkedList.
I read that the goal of merging LinkedList with HashTable is merging advantages of LinkedList (optimal enumeration of adjacency list of vertex) and HashTable (fast searching and adding edges).
I'm wondering about two things:
Would it be better using HashTable linked to another HashTable?
Any other suggestion? If I use HashTable, what would be the best way to solve collisions? I was thinking about Separate Chaining.
I assume that you desired Graph structure would be a HashTable<Vertex,ArrayList<Pair<Vertex,Float>>> mapping each vertex to its adjacent together with an edge weight.
You can use an ArrayList since you don't need to remove processed edges from the adjacency list.
In general I would not recommend linking the HashTable to a second one due to memory usage because the algorithm processes all adjacent edges of a vertex. Only if you wanted to remove a processed edge, it would help you to remove the edge for the other direction.
Note that while the HashMap + ArrayList approach is space efficient and sufficient for this algorithm to run in O(V^2), it is not recommended for dense graphs when many edge lookups are required. Checking whether an edge from A to B exists is linear in the number of adjacent vertices of A or B. If you want to retrieve them in O(1), you would want a second HashTable to store the edges. An example is given in the JGraphT Library.
Note also that it's generally recommended to use HashMap over HashTable