1

I have a class Node similar to Java's class Point with x and y coordinates, which I paint onto a JPanel. I'm trying to create a minimum spanning tree for a set of such nodes on a Euclidean graph, which I would then paint onto the panel as well. But I can't really figure out the data structure I'd need to do create the tree efficiently in the first place.

I've tried using LinkedLists and ArrayLists to implement Prim's algorithm, but they seem to make things overly complicated. What data structure should I be looking into for this instead?

u3l
  • 3,342
  • 4
  • 34
  • 51
  • use a [PriorityQueue](http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html)? – Niklas B. Mar 03 '14 at 17:29
  • What's with the [tag:traveling-salesman] tag? MST != TSP route (an MST doesn't even produce a path at all). Have you looked for an open-source Java MST implementation? – Bernhard Barker Mar 03 '14 at 17:45
  • Okay, I just put that in there because i'm using a MST to create a complete hamiltonian cycle (it would be have at most 2 times the optimal cost). I'll remove the tag though. I've seen a couple Java implementations, but they're very confusing to me, so I'm just trying to create one from scratch to try to understand it. – u3l Mar 03 '14 at 17:50

1 Answers1

0

Graph can be represented by adjacency list. I generally use Vector to create adjacency lists. They are very convenient to handle. Also use PriorityQueue to get minimum path cost.

Shashwat Kumar
  • 5,159
  • 2
  • 30
  • 66
  • What would be the difference between using a Vector or ArrayList; I was under the impression that the former was simply a synchronized version of the latter. I already tried using an `ArrayList` (since I thought using either wouldn't matter), but failed to do so... it doesn't seem like i'm implementing it as I should be. – u3l Mar 03 '14 at 17:40
  • I have always use Vector only. ArrayList would also serve the same I suppose. – Shashwat Kumar Mar 03 '14 at 17:43
  • @Trust http://stackoverflow.com/questions/1386275/why-is-java-vector-class-considered-obsolete-or-deprecated – effeffe Mar 03 '14 at 18:07
  • I understand the differences; I simply meant that in this case, they are essentially the same (I think). – u3l Mar 03 '14 at 18:14