java - 我想用java写一个prim的算法

Question

实际上，我想知道 prim 和 Dijkstra 算法的含义。如果有人可以教如何用 JAVA 编写它，我将不胜感激。我试图理解某人的 prim 算法代码，但我卡在了某个地方。

下面显示的代码是一个随机矩阵。我想继续编写 prim 的算法。有没有人可以帮忙？

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

score 6 · Accepted Answer

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