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/包summary.html

我敢肯定，没有这些算法会得到你想要你想要开箱即用，所以你必须自己编写代码，但我可以从编码上jgrapht的顶部经验告诉你，而不是起点从无到有是一个容易得多。还有一个斐波那契堆类，大概与实施帮助Prim算法。

如果您需要算法本身的帮助，还有许多与百科词条的算法，有详细的说明和伪代码。的最小生成树文章链接到它们。

Answer 2

荣格具有这个的实现。

Answer 3

ClosestFirstIterator 可以帮助你。它建立使用斐波那契堆而遍历顶点的生成树。

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);

Answer 4

在JGraphT库的最新版本有一个MST算法的各种选择，没有必要实施一个从头开始。

在下面的代码工作与Java 8和JGraphT版本1.3.0。它计算使用通过（a）的Prim，（b）中的Kruskal和（c）Borůvka算法较小的图形的最小生成树。有关不同的算法的细节可以在维基百科文章有关 MST问题中找到。

package org.myorg.mstdemo;

import org.jgrapht.Graph;
import org.jgrapht.alg.spanning.BoruvkaMinimumSpanningTree;
import org.jgrapht.alg.spanning.KruskalMinimumSpanningTree;
import org.jgrapht.alg.spanning.PrimMinimumSpanningTree;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.builder.GraphTypeBuilder;
import org.jgrapht.util.SupplierUtil;

/**
 * MST demo
 */
public class App {

    public static void main(String[] args) {

        Graph<String, DefaultWeightedEdge> graph = GraphTypeBuilder
                .undirected()
                .weighted(true)
                .allowingMultipleEdges(false)
                .allowingSelfLoops(false)
                .vertexSupplier(SupplierUtil.createStringSupplier())
                .edgeSupplier(SupplierUtil.createDefaultWeightedEdgeSupplier())
                .buildGraph();

        String v0 = graph.addVertex();
        String v1 = graph.addVertex();
        String v2 = graph.addVertex();

        DefaultWeightedEdge e1 = graph.addEdge(v0, v1);
        DefaultWeightedEdge e2 = graph.addEdge(v1, v2);
        DefaultWeightedEdge e3 = graph.addEdge(v0, v2);

        graph.setEdgeWeight(e1, 100d);
        graph.setEdgeWeight(e2, 5d);
        graph.setEdgeWeight(e3, 1d);

        System.out.println("Prim:");
        for(DefaultWeightedEdge e: new PrimMinimumSpanningTree<>(graph).getSpanningTree()) { 
            System.out.println(e);
        }

        System.out.println("Kruskal:");
        for(DefaultWeightedEdge e: new KruskalMinimumSpanningTree<>(graph).getSpanningTree()) { 
            System.out.println(e);
        }

        System.out.println("Borůvka:");
        for(DefaultWeightedEdge e: new BoruvkaMinimumSpanningTree<>(graph).getSpanningTree()) { 
            System.out.println(e);
        }

    }

}