牛客网AB14 最小生成树

import java.util.*;


public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] cost = {{5,3,8},{1,3,6},{2,5,4},{2,3,5},{4,5,6},{3,4,3},{2,4,8},{1,2,2},{1,4,5},{5,6,2}};
        System.out.println(solution.miniSpanningTree(6 ,10 ,cost));
    }

    
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here

        // 存储所有的点
        HashSet pointList = new HashSet<>();
        // 存储所有的边
        List edgeList = new ArrayList<>();

        // 定位出距离两个点之间距离最小的边
        Arrays.sort(cost, (o1, o2) -> o1[2] - o2[2]);

        // 把所有的边加入到结构集中
        for (int[] ints : cost) {
            edgeList.add(ints);
        }

        int res = edgeList.get(0)[2];
        // 先把两边距离最小的两天边加入到点集合中
        pointList.add(edgeList.get(0)[0]);
        pointList.add(edgeList.get(0)[1]);

        while (true){
            // 一直遍历找，找到于两条边相邻的点
            for (int i= 1; i < edgeList.size(); i++){
                // 找到与两条边相邻的顶点,并且这个边还是与一边相邻，另一边没有出现过
                if ((pointList.contains(edgeList.get(i)[0]) && !pointList.contains(edgeList.get(i)[1])) ||
                        ((pointList.contains(edgeList.get(i)[1])) && !pointList.contains(edgeList.get(i)[0]))){
                    res += edgeList.get(i)[2];
                    // 把找到的这条边加入到结果集中
                    pointList.add(edgeList.get(i)[0]);
                    pointList.add(edgeList.get(i)[1]);
                    // 删除这个边
                    edgeList.remove(edgeList.get(i));
                    break;
                }
            }
            // 全部村子都访问过了
            if (pointList.size() == n){
                break;
            }
        }
        return res;
    }

}