题解 | #最小生成树#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
    blank     * @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    //边的定义
    static class Edge {
        int src;
        int dest;
        int weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    //prime算法实现
    public int miniSpanningTree(int n, int m, int[][] cost) {
        int[][] doubleCost = new int[2 * m][3];
        int i = 0;
        for (int[] c : cost) {
            doubleCost[i] = c;
            doubleCost[i + 1][0] = c[1];
            doubleCost[i + 1][1] = c[0];
            doubleCost[i + 1][2] = c[2];
            i += 2;
        }


        //贪心算法，局部最优
        //起始节点集合与目的节点集合
        Set<Integer> srcSet = new HashSet<>();
        //初始化两个集合
        srcSet.add(1);
        //从srcSet到destSet集合的边
        //定义优先级队列与初始优先级队列
        PriorityQueue<Edge> minHeap = new PriorityQueue<>(
            Comparator.comparingInt(a -> a.weight)
        );
        for (int[] c : doubleCost) {
            if (c[0] == 1) {
                minHeap.offer(new Edge(1, c[1], c[2]));
            }
        }
        int retWeight = 0;
        while (!minHeap.isEmpty()) {
            Edge minEdge = minHeap.poll();
            int dest = minEdge.dest;
            //判断dest是否被标记过
            if (!srcSet.contains(dest)) {
                retWeight += minEdge.weight;
                //目的节点被标记：加入srcSet
                srcSet.add(dest);
                //添加新增起始顶点的所有直接连通的边
                for (int[] c : doubleCost) {
                    if (c[0] == dest) {
                        minHeap.offer(new Edge(dest, c[1], c[2]));
                    }
                }
            }
        }
        return retWeight;
    }
}