Prim算法

LeetCode 1584 连接所有点的最小费用

给你一个points数组，表示 2D 平面上的一些点，其中points[i] = [xi, yi]。
连接点[xi, yi] 和点[xj, yj]的费用为它们之间的 曼哈顿距：|xi - xj| + |yi - yj|，
其中|val|表示val的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有一条简单路径时，才认为所有点都已连接。

public class MinCostToConnectAllPoints {

    /**
     * Prim算法
     *
     *执行结果：通过
     * 执行用时：1628 ms, 在所有 Java 提交中击败了5.05%的用户
     * 内存消耗：88.4 MB, 在所有 Java 提交中击败了14.11%的用户
     * 通过测试用例：72 / 72
     *
     * @param points
     * @return
     */
    public int minCostConnectPoints(int[][] points) {
        PriorityQueue<Edge> priorityQueue = new PriorityQueue(new Comparator<Edge>() {
            @Override
            public int compare(Edge edge1, Edge edge2) {
                return edge1.weight - edge2.weight;
            }
        });
        HashSet<Node> nodeHashSet = new HashSet<>();
        int result = 0;
        Graph graph = convert(points);
        Node node = graph.nodes.get(0);
        nodeHashSet.add(node);
        for (Edge edge : node.edges) {
            priorityQueue.add(edge);
        }

        while (!priorityQueue.isEmpty()) {
            Edge minEdge = priorityQueue.poll();
            if (!nodeHashSet.contains(minEdge.to)) {
                nodeHashSet.add(minEdge.to);
                for (Edge edge : minEdge.to.edges) {
                    priorityQueue.add(edge);
                }
                result += minEdge.weight;
            }
        }

        return result;
    }

    public Graph convert(int[][] points) {
        Graph graph = new Graph();
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                if (!graph.nodes.containsKey(j)) {
                    Node node = new Node(j);
                    graph.nodes.put(j, node);
                }
                if (j != i) {
                    int length = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                    Edge edge = new Edge(length, graph.nodes.get(i), graph.nodes.get(j));
                    graph.nodes.get(i).edges.add(edge);
                }
            }
        }
        return graph;
    }

    public class Node {
        public int val;
        public ArrayList<Edge> edges;

        public Node() {
        }

        public Node(int val) {
            this.val = val;
            this.edges = new ArrayList<Edge>();
        }
    }

    public class Edge {
        public int weight;
        public Node from;
        public Node to;

        public Edge() {
        }

        public Edge(int weight, Node from, Node to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }
    }

    public class Graph {
        public HashMap<Integer, Node> nodes;


        public Graph() {
            this.nodes = new HashMap<Integer, Node>();
        }
    }
}