Java实现普利姆算法Prim求最小生成树（算法设计与分析作业）

package package1;

import java.util.Arrays;

public class alg {
   
// 初始化图，g保存图，n保存点坐标和权值
    public static void initGraph(int[][] g, int[][] n) {
   
        for (int[] ints : n) {
   
            g[ints[0] - 1][ints[1] - 1] = ints[2];
            g[ints[1] - 1][ints[0] - 1] = ints[2];
        }
        for (int[] ints : g) {
   
            System.out.println(Arrays.toString(ints));
        }
    }
//算法函数
    public static void prim(int[][] g) {
   
        int[] minList = new int[g.length];
        int p_m = 0;
        int[][] G = new int[g.length][g[0].length];
        System.arraycopy(g, 0, G, 0, g.length);
        System.arraycopy(g[0], 0, G[0], 0, g[0].length);
        for (int i = 0; i < g.length - 1; i++) {
   
            int[] k = new int[2];
            if (i == 0) {
   
                minList[p_m] = 0;
                p_m++;
                k = min(G, minList);
                G[k[0]][k[1]] = Integer.MAX_VALUE;
                G[k[1]][k[0]] = Integer.MAX_VALUE;
                minList[p_m] = k[1];
                p_m++;
            } else {
   
                do {
   
                    k = min(G, minList);
                    G[k[0]][k[1]] = Integer.MAX_VALUE;
                    G[k[1]][k[0]] = Integer.MAX_VALUE;
                } while (isIn(minList, k[1]) && isIn(minList, k[0]) && i != g.length - 2);
                if (p_m < g.length) {
   
                    minList[p_m] = k[1];
                    p_m++;
                }
            }
            char p1 = (char) (k[0] + 97);
            char p2 = (char) (k[1] + 97);
            System.out.println((k[0] + 1) + "" + p1 + "<--->" + p2 + (k[1] + 1));

        }
    }
//求num中的最小值，list保存num中需要求的行数
    public static int[] min(int[][] num,int[] list) {
   
        int t = Integer.MAX_VALUE;
        int[] R = new int[2];
        for (int i = 0; i < num.length; i++) {
   
            if(!isIn(list,i)){
   
                continue;
            }
            for (int j = 0; j < num[i].length; j++) {
   
                if (num[i][j] < t && num[i][j] != 0) {
   
                    R[0] = i;
                    R[1] = j;
                    t = num[i][j];
                }
            }
        }
        return R;
    }
//判断tar是否在nums中
    public static boolean isIn(int[] nums, int tar) {
   
        for (int n : nums) {
   
            if (tar == n) {
   
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
   
        int[][] n = {
   {
   1, 2, 3}, {
   1, 5, 6}, {
   1, 6, 5}, {
   2, 3, 1}, {
   2, 6, 4}, {
   3, 4, 6}, {
   3, 6, 4}, {
   4, 5, 8}, {
   4, 6, 5}, {
   5, 6, 2}};
        int[][] g = new int[6][6];
        System.out.println("------------------------");
        initGraph(g, n);
        prim(g);

        int[][] n1 = {
   {
   1,2,5},{
   1,5,2},{
   1,3,7},{
   2,4,6},{
   2,5,3},{
   3,4,4},{
   3,5,4},{
   4,5,5}};
        int[][] g1 = new int[5][5];
        System.out.println("------------------------");
        initGraph(g1,n1);
        prim(g1);

        int[][] n2 = {
   {
   1,2,3},{
   1,4,4},{
   1,3,5},{
   2,5,3},{
   2,6,6},{
   4,3,2},{
   4,8,5},{
   4,5,1},{
   6,5,2},{
   6,10,5},{
   7,3,4},{
   7,8,3},{
   7,11,6},{
   9,8,6},{
   9,5,4},{
   9,10,3},{
   9,12,5},{
   11,12,8},{
   11,8,7},{
   12,10,9}};
        int[][] g2 = new int[12][12];
        System.out.println("------------------------");
        initGraph(g2,n2);
        prim(g2);
    }
}