1

グラフの隣接行列から最小スパニング ツリーを取得する方法を理解するのを手伝ってください! 私はそれについて Java でコースワークを書いています。締め切りは 2010 年 12 月 16 日ですが、失敗するだろうと感じています。今、私のプログラムは次のことができます：

  1. ノードを描画
  2. エッジを描く
  3. エッジの重みを使用して、図面の地下にグラフの隣接行列を生成します
  4. ノードに接続された最小エッジを見つける
  5. 他のいくつかのテスト/テスト済み機能があります

しかし、Java で Prim/Kruskal アルゴリズムを実現する方法がわかりません。Googleでいくつかの解決策を見つけようとしましたが、.objファイルを動作させる必要があるJavaアプレットしか見つけられず、実行できません。

グラフの隣接行列を生成して出力する単純なコンソール Java パターンを作成します。次のようなグラフの最小スパニング ツリーの隣接行列を返す関数を誰でも追加できますか。

public static int[][] mst(int[][] graph, int n) {
    ...
}

どこ：

  • グラフ - n で生成されたグラフ
  • 頂点 (ノード) の量

前もって感謝します！

4

2 に答える 2

1

誰かが隣接行列を実装した MST を探しているなら、私の Java のサンプル コードがあります。ジャンクボットの回答に詳細が欠けているため、投稿します。これは O(n^2) で実行されるため、MST を見つけるための高密度/完全なグラフには Prim のアルゴリズムが最適です。

    public void MST-Prim()
    {
    int[] source = new int[numberOfVertices]; // i-th element contains number of source vertex for the edge with the lowest cost from tree T to vertex i
    double[] dist = new double[numberOfVertices]; //i-th element contains weight of minimal edge connecting i with source[i] 
    indicators = new boolean[numberOfVertices];  //if true, vertex i is in tree T

    // Mark all vertices as NOT being in the minimum spanning tree
    for (int i = 0; i < numberOfVertices; i++)
    {
        indicators[i] = false;
        dist[i] = Double.POSITIVE_INFINITY;
    }

     //we start with vertex number 0
    indicators[0] = true;
    dist[0] = 0;
    int bestNeighbour = 0;// lastly added vertex to the tree T 
    double minDist; 

    for (int i = 0; i < numberOfVertices - 1; i++)
    {
        minDist = Double.POSITIVE_INFINITY;

        for (int j = 0; j < numberOfVertices; j++) // fill dist[] based on distance to bestNeighbour vertex
        {
            if (!indicators[j])
            {
                double weight = fullGraph.getEdgeWeight(bestNeighbour, j);

                if (weight < dist[j])
                {
                    source[j] = bestNeighbour;
                    dist[j] = weight;
                }
            }
        }

        for (int j = 0; j < numberOfVertices; j++) // find index of min in dist[]
        {
            if (!indicators[j])
            {
                if (dist[j] < minDist)
                {
                    bestNeighbour = j;
                    minDist = dist[j];
                }
            }
        }

        if (bestNeighbour != 0)
        {//add the edge (bestNeighbour, dist[bestNeighbour]) to tree T
            addEdgeToTree(new GraphEdge(fullGraph.getNode(source[bestNeighbour]), fullGraph.getNode(bestNeighbour),
                    dist[bestNeighbour]));
            indicators[bestNeighbour] = true;
        }

    }

}
于 2012-04-04T22:55:10.813 に答える
1

現時点であなたのプログラムが Disjoint Set Data Structure を処理できない場合、おそらく Prim を使用したいと思うでしょう。

Prim を実行するのに必要なほとんどのことは既に実行できるので、疑似コードで説明します。

int bestDist[N]
int mst[N][N]
int cameHere[N]
bool done[N]
FOR i = 0..N-1:
 bestDist[i] = INFINITY
 done[i] = false
 FOR j=0..N-1:
  mst[i][j] = INFINITY

// start at any node
bestDist[0] = 0;
FOR i = 0..N-1:
 bestNode = INFINITY
 bestNodeDist = INFINITY

 IF bestNode != 0:
  mst[cameHere[bestNode]][bestNode] = graph[cameHere[bestNode]][bestNode]

 // find closest node
 FOR j= 0..N-1:
  IF !done[j] AND bestDist[j] < bestNodeDist:
   bestNode = j
   bestNodeDist = bestNodeDist[j]

 // update surrounding nodes
 FOR j=0..N-1:
  IF !done[j] AND bestNodeDist + graph[bestNode][j] < bestDist[j]:
   bestDist[j] = bestNodeDist + graph[bestNode][j]
   cameHere[j] = bestNode

return mst

これは O(N^2) で実行されますが、O(E log E) で実行することもできます。ここで、ヒープを使用する場合は E = num エッジです。

于 2011-01-20T11:28:27.750 に答える