0

実は、プリムとダイクストラアルゴリズムの意味を知りたいです。誰かがJAVAでそれを書く方法を教えていただければ幸いです。プリムのアルゴリズムの誰かのコードを理解しようとしましたが、どこかで行き詰まりました。

以下に示すコードはランダム行列です。そして、プリムのアルゴリズムを書き始めたいと思います。誰か助けてくれる人はいますか？

 import java.util.*;
 class RandomGraph
 {
    public static Scanner br = new Scanner(System.in);
    static int w [][];
    static int n;
    static int i, j;

    public static void main (String[] args)
    {
        System.out.println("Find the shortest edge");
        System.out.println("\nEnter the number of the vertices: ");
        n = br.nextInt();
        w = new int[n+1][n+1];
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                if((i!=j))
                {
                w[i][j] = w[j][i]= 1+(int)(Math.random()*9);
                }
                else if(i == j)
                {
                    w[i][j] = w[j][i] = 0;
                }
            }
        Graph();
    }

    static void Graph()
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                System.out.print("  "+w[i][j]+"  ");
            }
        System.out.println();
        }
    }
}
4

2 に答える 2

6

Java での Prims アルゴリズムの実装 - 最小コスト スパニング ツリー

public class Prim {
    int weightArray[][] = new int[20][20];
    int visited[] = new int [20];
    int d[] = new int[20];
    int p[] = new int[20];
    int verticeCount, edgeCount;
    int nodeA, nodeB, weight;
    int current, total, mincost;


    public static void main(String args[]) throws IOException {

        // Instantiate the graph based on input
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("\nEnter number of vertices: ");
        verticeCount = Integer.parseInt(buf.readLine());
        System.out.print("\nEnter number of edges: ");
        edgeCount = Integer.parseInt(buf.readLine());
        for (int i = 1; i <= verticeCount; i++) {
            for(int j = 1; j <= verticeCount; j++) {
                weightArray[i][j] = 0;
            }
        }

       for (int i = 1; i <= verticeCount; i++) {
           p[i] = visited[i] = 0;
           d[i] = 32767;
        }

        for (int i = 1; i <= edgeCount; i++) {
            System.out.print("\nEnter edge nodeA, nodeB and weightArray weight: ");
            nodeA=Integer.parseInt(in.readLine());
            nodeB=Integer.parseInt(in.readLine());
            weight=Integer.parseInt(in.readLine());
            weightArray[nodeA][nodeB] = weightArray[nodeB][nodeA] = weight;
        }
        // End of graph instantiation

        current = 1;
        d[current] = 0;
        total = 1;
        visited[current] = 1;
        while( total != verticeCount) {
            for (int i = 1; i <= verticeCount; i++) {
                if ( weightArray[current][i] != 0) {
                    if( visited[i] == 0) { 
                        if (d[i] > weightArray[current][i]) {
                            d[i] = weightArray[current][i];
                            p[i] = current;
                        }
                    }
                }
            }
            mincost=32767;
            for (int i = 1 ; i <= verticeCount; i++) {
                if (visited[i] == 0) {
                    if (d[i] < mincost) {
                        mincost = d[i];
                        current = i;
                    }
                }
            }
            visited[current]=1;
            total++;
        }

        mincost=0;
        for(i=1;i<=verticeCount;i++)
        mincost=mincost+d[i];

        System.out.print("\n Minimum cost="+mincost);
        System.out.print("\n Minimum Spanning tree is");

        for(i=1;i<=verticeCount;i++)
        System.out.print("\n vertex" +i+"is connected to"+p[i]);
    }
}
于 2013-08-02T05:20:41.897 に答える
0

プリムのアルゴリズム:

Prim のアルゴリズムは、接続された重み付き無向グラフの最小スパニング ツリーを見つける貪欲なアルゴリズムです。これは、すべての頂点を含むツリーを形成するエッジのサブセットを見つけ、ツリー内のすべてのエッジの合計重みが最小になることを意味します。

意味：

  • グラフから任意に選択された単一の頂点を含むツリーを作成します
  • グラフ内のすべてのエッジを含むセットを作成します

  • セット内のすべてのエッジがツリー内の 2 つの頂点を接続するまでループします

    • ツリー内の頂点をツリー内にない頂点と接続する最小の重みを持つエッジをセットから削除します

  • そのエッジをツリーに追加します

Wiki リンク - http://en.wikipedia.org/wiki/Prim 's_algorithm

リンクの例:

http://github.com/phishman3579/java-algorithms-implementation/blob/master/src/com/jwetherell/algorithms/graph/Prim.java

http://sourcecodesforfree.blogspot.in/2013/05/10-prims-algorithm.html

于 2013-08-02T05:20:27.740 に答える