Java: Data structure for minimum spanning tree

Question

My project is to implement minimum spanning tree using java. I aim to use Prim's algorithm to do the task.

The definition of the graph is G = (V, E) where V is the set of pins, E is the set of possible interconnections between pairs of pins, and for each edge (u,v) in E we have a weigh w(u,v) specifying the cost to connect u and v.

My idea is to use two hashmaps. First would have pin as a key and a list of neighbours as value. The second hashmap would take list of edge (u,v) as a key and the value would be its weight.

What do you think is the best way to store the graph?

Answer 1

Graphs are generally (without regard to the algorithm used with those graphs) stored as either :

• adjacency lists,
• adjacency matrices,
• incidence lists,
• incidence matrices.

All have their advantages and disadvantages concerning memory usage and time required to traverse them. Wikipedia has a great write-up on graph representations in computers.

Answer 2

Look on wikipedia. You have different data structures available as well as the inherited complexities

Answer 3

For both Kruskal’s and Prim’s minimum spanning tree algorithms adjacency-list representation of the graph is enough. It's more efficient in memory usage than matrice's approach. So it's a good choise in your case.