Prim算法

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        List<List<int[]>> grap = new ArrayList<>();
        for(int i=0;i<=n;i++)
            grap.add(new ArrayList<>());
        for(int[] c:cost){
            grap.get(c[0]).add(new int[]{c[1],c[2]});
            grap.get(c[1]).add(new int[]{c[0],c[2]});
        }
        PriorityQueue<int[]> minEdgeHeap = new PriorityQueue<>((a,b)->a[2]-b[2]);
        for(int[] edges:grap.get(1)){
            minEdgeHeap.add(new int[]{1,edges[0],edges[1]});
        }
        boolean[] flag = new boolean[n+1];
        flag[1] = true;
        int result=0;//最终最小路径长
        while(!minEdgeHeap.isEmpty()){
            int[] edges = minEdgeHeap.poll();
            int from = edges[0],to = edges[1],min = edges[2];
            if(flag[to])//判断优先队列中的最小路径的顶点是否已经纳入
                continue;
            flag[to] = true;
            result+=min;
            for(int[] nei:grap.get(to)){
                if(flag[nei[0]]==true) //添加未纳入最小生成树的点
                    continue;
                minEdgeHeap.add(new int[]{to,nei[0],nei[1]});
            }
        }
        return result;
  
        
    }
}

注意： 1.算法中两次判断顶点是否纳入最小生成树。第一次判断是因为有的边两个顶点已纳入最小生成树，但该边当时不是最小的，没有被弹出，会影响之后获取最小边。 第二次判断是将顶点未纳入最小生成树的边加入。 2.使用PriorityQueue可以减少最小值的判断，方便书写。使用时可以自定义比较器排序，默认为自然排序。

## Kruskal算法

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        int[] path = new int[n+1];//记录最小生成树路径
        int total = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->(a[2]-b[2]));
        for(int i = 0;i<m;i++)
            queue.add(cost[i]);
        for(int i=1;i<=n;i++)
            path[i] = 0;
        while(!queue.isEmpty()){
            int[] c = queue.poll();
            int from = find(path,c[0]);
            int to = find(path,c[1]);
            if(from!=to){//该边不会与已经纳入的边构成环
                path[from] = to;
                total+=c[2];
            }
        }
        return total;
        
        
    }
    public int find(int[] path,int f){
        while(path[f]>0)
            f = path[f];
        return f;
    }
}

总结：
1.卡鲁斯卡尔算法是将边按照权值大小排序，在构建最小生成树时需要考虑边是否会构成环路。