算法1 prim算法

// prim算法
import java.util.*;
public class Main {
    static int INF = 0x3f3f3f3f;// 无穷大
    static int N = 110;
    static int[][] g = new int [N][N];//点与点之间的距离
    static boolean[] use = new boolean[N];//点是否加入集合
    static int [] d = new int [N];//点到集合的距离
    static int n,ans = 0;

    static void prim(){
        Arrays.fill(d, INF);
        d[1] = 0;
        for(int i = 1;i <= n;i++){
            int t = -1;
            for(int j =1;j <= n;j++){
                // 找到离集合最短的点
                if(!use[j] && (t==-1 || d[t] > d[j])){
                    t = j;
                }
            }

            if (i > 1) ans += d[t];
            use[t] = true;
            // t点加入到集合后，更新其他点到集合的距离
            for(int j = 1;j <= n;j++){
                d[j] = Math.min(d[j], g[t][j]);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                g[i][j] = sc.nextInt();
            }
        }

        prim();
        System.out.println(ans);
    }
}

算法2 kruskal算法

// kruskal算法
import java.util.*;
public class Main {
    static int INF = 0x3f3f3f3f;// 无穷大
    static int N = 110,M = 10010;// 最大 点数/边数
    static int n,m;// n个点 m条边
    static int idx = 0;// 使用的边数
    static int [] p = new int [N];//记录祖宗节点
    static Edge[] edge = new Edge[M];//边的属性

    static class Edge{
        int a,b,w;
        public Edge(int a,int b,int w){
            this.a = a;this.b = b;this.w = w;
        }
    }

    static int find(int x){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    static int kruskal(){
        // 按权值升序排序
        Arrays.sort(edge, 0, m, (o1,o2)->o1.w-o2.w);

        // 开始祖宗指向自己
        for(int i = 1;i <= n;i++) p[i] = i;
        int ans = 0;
        for(int i = 0;i < m;i++){
            int a = edge[i].a;
            int b = edge[i].b;
            int w = edge[i].w;
            // 查找a和b的父节点
            a = find(a);b = find(b);
            // a,b不在一个集合
            if(a != b){
                p[a] = b;//将a加入到b中
                ans += w;//加上a->b边的权值
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();m = n*(n-1)/2;
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                int c = sc.nextInt();
                // 加入i < j的边,共n-1 n-2 n-3 ... 1 条
                if(i < j) edge[idx++] = new Edge(i, j, c);
            }
        }
        int result = kruskal();
        System.out.println(result);
    }
}