Java: Minimum spanning tree with JGraphT?

Question

I have a problem that can essentially be viewed as a graph. I'm considering using JGraphT to implement it instead of rolling my own. What would be the best way to get a minimum spanning tree out of a graph using JGraphT?

Answer 1

Unfortunately, I don't know enough graph theory to give you a complete, direct answer, but I have used jgrapht in a few projects, so maybe this will help.

The list of algorithms included with jgrapht is here: http://www.jgrapht.org/javadoc/org/jgrapht/alg/package-summary.html, and you can also find graph traversals implemented as iterators (if that is any help) here: http://www.jgrapht.org/javadoc/org/jgrapht/traverse/package-summary.html

I'm pretty sure none of those algorithms will get you want you want out of the box, so you'd have to code it yourself, but I can tell you from experience that coding on top of jgrapht as opposed to starting from scratch is A LOT easier. There is also a FibonacciHeap class that would presumably help with implementing Prim's algorithm.

If you need help with the algorithm itself, there are a number of algorithms with Wikipedia entries, with detailed descriptions and pseudocode. The Minimum spanning tree article links to them.

Answer 2

Jung has an implementation of this.