2

基本的にグラフとして表示できる問題があります。私は自分自身をロールバックする代わりに、JGraphT を使用して実装することを検討しています。JGraphT を使用してグラフから最小スパニング ツリーを取得する最良の方法は何でしょうか?

4

4 に答える 4

5

残念ながら、私はあなたに完全で直接的な答えを与えるのに十分なグラフ理論を知りませんが、いくつかのプロジェクトで 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 のアルゴリズムの実装に役立つと思われるFibonacciHeapクラスもあります。

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

于 2009-12-01T16:48:51.307 に答える
2

ユングはこれを実装しています。

于 2011-05-31T08:01:21.513 に答える
1

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);
于 2011-11-24T13:49:50.063 に答える
0

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

    }

}
于 2019-04-26T10:12:10.363 に答える