ジャバ: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 上でコーディングすることは、ずっと簡単です。もあります。 フィボナッチヒープ おそらく Prim のアルゴリズムの実装に役立つクラスです。

アルゴリズム自体についてサポートが必要な場合は、詳細な説明と疑似コードを含む、Wikipedia のエントリに多数のアルゴリズムがあります。の 最小スパニングツリー記事 それらへのリンク。

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アルゴリズムのためにゼロから1を実装する必要がさまざまな選択肢がありません。

次のコードは、Java 8とJGraphTバージョン1.3.0で動作します。これは、（a）は、プリム、（b）は、クラスカルおよび（c）Borůvkaによってアルゴリズムを使用して小さなグラフのスパニングツリー最小値を計算します。異なるアルゴリズムの詳細については、 MST問題について Wikipediaの記事で見つけることができます。

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

    }

}