题解 | #最小生成树#

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
        //常规prim是针对点来遍历，时间复杂度高，可以将边存储，
        //首先将边按照权值将边从小到大排序
        Arrays.sort(cost, Comparator.comparingInt(o -> o[2]));
        //新建一个ArrayList存储边，以便于遍历时将不会用到的边删除，即剪枝。
        ArrayList<int[]> edges = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            edges.add(cost[i]);
        }
        //新建一个集合存储点，为了方便终止遍历，使用hashset
        HashSet<Integer> vers = new HashSet<>();
        vers.add(edges.get(0)[0]);
        vers.add(edges.get(0)[1]);
        int sum = edges.get(0)[2];
        //新建一个集合用来剪枝，删除不会再用的边
        ArrayList<Integer> delete = new ArrayList<>();
        while (vers.size()<n){
            for (int i = 0; i < edges.size(); i++) {
                if(vers.contains(edges.get(i)[0]) && vers.contains(edges.get(i)[1])){
                    //如果这条边的两个点都到访过了，那以后也就不用了
                    delete.add(i);
                } else if (!vers.contains(edges.get(i)[0]) && !vers.contains(edges.get(i)[1])) {
                    //啥也不做，纯粹是不想写太长的条件，排除掉这个边的两点都没访问过的情况
                } else{
                    //因为边集合已经排过序，所以遇到的第一个符合要求的就是最短的，将其设为访问，然后跳出这次循环
                    vers.add(edges.get(i)[0]);
                    vers.add(edges.get(i)[1]);
                    sum += edges.get(i)[2];
                    delete.add(i);
                    break;
                }
            }
            //将不用的边删除
            for (int i = delete.size()-1; i >= 0; i--) {
                edges.remove(delete.get(i).intValue());
            }
            delete.clear();
        }
        return sum;
    }
}