图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的算法

如果您需要有关算法本身的帮助，那么有许多包含Wikipedia条目的算法，有详细的描述和伪代码。{a4}链接到它们

Answer 2

JGraphT库的最新版本为MST算法提供了多种选择，无需从头实现

以下代码适用于Java8和JGraphT版本1.3.0。它使用（a）Prim，（b）Kruskal和（c）Borůvka的算法计算一个小图的最小生成树。关于不同算法的详细信息可以在维基百科关于mst problem的文章中找到

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

    }

}

Answer 3

Jung实现了这一点

Answer 4

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