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

我很确定这些算法都不能让你开箱即用，所以你必须自己编码，但我可以根据经验告诉你，在 jgrapht 之上编码而不是开始从头开始要容易得多。还有一个FibonacciHeap可能有助于实现 Prim 算法的类。

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