0

クラスカルとプリムのアルゴリズムを使用して、指定された無向加重グラフの MST を見つけるプログラムを作成しようとしています。クラスカルのアルゴリズムをプログラムにうまく実装できましたが、プリムのアルゴリズムに問題があります。より正確に言えば、Prim 関数を実際に構築して、グラフ内のすべての頂点を反復処理する方法がわかりません。プログラムの実行中に IndexOutOfBoundsException エラーが発生します。私がこれまでに行ったことを他の人が理解するのにどれだけの情報が必要かはわかりませんが、役に立たない情報が多すぎないことを願っています.

これは私がこれまでに持っているものです:

、およびクラスGraphがあります。EdgeVertex

  • 頂点クラスは、ほとんどの場合、頂点の名前 (番号) を含む単なる情報ストレージです。

  • Edge クラスは、gets parameters を持つ新しい Edge を作成できます(Vertex start, Vertex end, int edgeWeight)。このクラスには、開始頂点、終了頂点、重みなどの通常の情報を返すメソッドがあります。

  • Graph クラスは、テキスト ファイルからデータを読み取り、新しい Edge を ArrayList に追加します。テキスト ファイルには、グラフに含まれる頂点の数も示され、それも保存されます。

クラスにはGraph、MST を計算するはずの Prim() メソッドがあります。

    public ArrayList<Edge> Prim(Graph G) {

    ArrayList<Edge> edges = G.graph; // Copies the ArrayList with all edges in it.
    ArrayList<Edge> MST = new ArrayList<Edge>();

    Random rnd = new Random();

    Vertex startingVertex = edges.get(rnd.nextInt(G.returnVertexCount())).returnStartingVertex(); // This is just to randomize the starting vertex.

    // This is supposed to be the main loop to find the MST, but this is probably horribly wrong..
    while (MST.size() < returnVertexCount()) {

        Edge e = findClosestNeighbour(startingVertex);
        MST.add(e);
        visited.add(e.returnStartingVertex());
        visited.add(e.returnEndingVertex());
        edges.remove(e);

    }

    return MST;
}

メソッド findClosesNeighbour() は次のようになります。

public Edge findClosestNeighbour(Vertex v) {

    ArrayList<Edge> neighbours = new ArrayList<Edge>();
    ArrayList<Edge> edges = graph;

    for (int i = 0; i < edges.size() -1; ++i) {

        if (edges.get(i).endPoint() == s.returnVertexID() && !visited(edges.get(i).returnEndingVertex())) {

            neighbours.add(edges.get(i));
        }
    }

    return neighbours.get(0); // This is the minimum weight edge in the list.
}

ArrayList<Vertex> visitedArrayList<Edges> graph新しいグラフを作成するときに構築されます。

Visited() メソッドは、移動しようとしている Vertex が Visited ArrayList に含まれているかどうかを確認する単純なブール値チェックです。私は独立してテストしましたfindClosestNeighbour()が、動作しているように見えましたが、誰かが何か問題を見つけた場合は、そのフィードバックも歓迎します.

主に、私の問題は Prim() メソッドで実際にメインループを構築することにありますが、必要な追加情報があれば喜んで提供します。

ありがとうございました。

編集: Prim() メソッドを使用した私の思考の流れを明確にするため。私がやりたいことは、まずグラフの開始点をランダム化することです。その後、その開始点に最も近い隣人を見つけます。次に、これらの 2 つのポイントを接続するエッジを MST に追加し、後で確認するために頂点を訪問済みリストに追加して、グラフにループが形成されないようにします。

スローされるエラーは次のとおりです。

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
    at java.util.ArrayList.rangeCheck(Unknown Source)
    at java.util.ArrayList.get(Unknown Source)
    at Graph.findClosestNeighbour(graph.java:203)
    at Graph.Prim(graph.java:179)
    at MST.main(MST.java:49)

203行目: return neighbour.get(0);in findClosestNeighbour()

179行目: Edge e = findClosestNeighbour(startingVertex);in Prim()

4

2 に答える 2

0 
Vertex startingVertex = edges.get(rnd.nextInt(G.returnVertexCount())).returnStartingVertex();

これは、頂点カウントを使用してエッジリストにインデックスを付け、頂点とエッジを混同します。

// This is supposed to be the main loop to find the MST, but this is probably horribly wrong..
while (MST.size() < returnVertexCount()) {

    Edge e = findClosestNeighbour(startingVertex);
    MST.add(e);
    visited.add(e.returnStartingVertex());
    visited.add(e.returnEndingVertex());
    edges.remove(e);
}

これは、毎回同じstartingVertexをfindClosestNeighbourに渡すべきではありません。

public Edge findClosestNeighbour(Vertex v) {

    ArrayList<Edge> neighbours = new ArrayList<Edge>();
    ArrayList<Edge> edges = graph;

    for (int i = 0; i < edges.size() -1; ++i) {

        if (edges.get(i).endPoint() == s.returnVertexID() && !visited(edges.get(i).returnEndingVertex())) {

            neighbours.add(edges.get(i));
        }
    }

    return neighbours.get(0); // This is the minimum weight edge in the list.
}

sここは何ですか？これは、エッジの重みを考慮しているようには見えません。最後のエッジをスキップし、エッジが無指向性の場合、終了頂点のみをチェックします。

于 2012-03-31T23:26:55.497 に答える