Java：使用JGraphT生成最小生成树？

Question

我有一个问题，基本上可以看作一个图。我正在考虑使用JGraphT来实现它，而不是滚动我自己的。使用JGraphT从图中获得最小生成树的最佳方法是什么？

Answer 1

不幸的是，我不知道足够的图论给你一个完整的，直接的答案，但我已经在几个项目中使用jgrapht，所以也许这会有所帮助。

包含jgrapht是这里的算法列表：http://www.jgrapht.org/javadoc/org/jgrapht/alg/package-summary.html，你还可以找到图遍历实现迭代器（如果这是任何帮助）在这里：http://www.jgrapht.org/javadoc/org/jgrapht/traverse/package-summary.html

我敢肯定，没有这些算法将让你想要开箱即用，所以你必须自己编写代码，但我可以从经验告诉你，在jgraph之上编写代码而不是从头开始更容易。还有一个FibonacciHeap类，可能有助于实施Prim的算法。

如果您需要算法本身的帮助，有许多关于维基百科条目的算法，包括详细的描述和伪代码。 Minimum spanning tree article链接到他们。

Answer 2

Jung有一个这样的实现。

Answer 3

ClosestFirstIterator可能会帮助你。它在遍历顶点时使用FibonacciHeap构建生成树。

ClosestFirstIterator提供方法getShortestPathLength（）和getSpanningTreeEdge（）来获取最小生成树的部分。

// instantiate the iterator 
ClosestFirstIterator<V,E> it = new ClosestFirstIterator<V,E>(graph, start_vertex); 

// iterate to build the tree 
while(it.hasNext()) 
    it.next(); 

// query 
double distance = getShortestPathLength(vertex); 
E next_edge = getSpanningTreeEdge(vertex);