用JGraphT实现最小生成树？

Question

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

Answer 1

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

http://www.jgrapht.org/javadoc/org/jgrapht/traverse/package-summary.html包含的算法列表在这里: jgrapht，您还可以在这里找到作为迭代器实现的图遍历(如果有帮助的话)：jgrapht

我非常肯定这些算法都不会得到你想要的开箱即用，所以你必须自己编码，但我可以根据经验告诉你，在jgrapht之上编码要比从头开始容易得多。还有一个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);