脚本宝典收集整理的这篇文章主要介绍了最低成本联通所有城市（Prim），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

想象一下你是个城市基建规划者，地图上有 N 座城市，它们按以 1 到 N 的次序编号。

给你一些可连接的选项 conections，其中每个选项 conections[i] = [city1, city2, cost] 表示将城市 city1 和城市 city2 连接所要的成本。（连接是双向的，也就是说城市 city1 和城市 city2 相连也同样意味着城市 city2 和城市 city1 相连）。

返回使得每对城市间都存在将它们连接在一起的连通路径（可能长度为 1 的）最小成本。该最小成本应该是所用全部连接代价的综合。如果根据已知条件无法完成该项任务，则请你返回 -1。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/connecting-cities-with-minimum-cost 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

边的方向敏感

每次选距已完成集合最短的边进行拓展

时间复杂度：O（nloge）

import java.util.*;

class Solution {
    public static int minimumCost(int n, int[][] connections) {
        if (connections == null || connections.length == 0 || connections[0].length == 0) {
            return 0;
        }
        Graph graph = new Graph();
        UnionSet unionSet = new UnionSet(n);
        for (int i = 0; i < connections.length; ++i) {
            graph.addEdge(connections[i][0], connections[i][1], connections[i][2]);
            graph.addEdge(connections[i][1], connections[i][0], connections[i][2]);
            unionSet.merge(connections[i][0], connections[i][1]);
        }

        if (unionSet.size() != 1) {
            return -1;
        }

        PriorityQueue<Graph.Edge> queue = new PriorityQueue<>(new Comparator<Graph.Edge>() {
            @Override
            public int compare(Graph.Edge o1, Graph.Edge o2) {
                return Integer.compare(o1.weight, o2.weight);
            }
        });

        Set<Graph.Node> visited = new HashSet<>();
        Set<Graph.Edge> resSet = new HashSet<>();
        for (Graph.Node node : graph.getNodeMap().values()) {
            if (!visited.contains(node)) {
                visited.add(node);
                for (Graph.Edge edge : node.nexts) {
                    queue.offer(edge);
                }
                while (!queue.isEmpty()) {
                    Graph.Edge edge = queue.poll();
                    Graph.Node to = edge.to;
                    if (!visited.contains(to)) {
                        visited.add(to);
                        resSet.add(edge);
                        for (Graph.Edge e : to.nexts) {
                            queue.offer(e);
                        }
                    }
                }
            }
        }

        return resSet.stream().mapToInt(Graph.Edge::getWeight).sum();
    }

    public static void main(String[] args) {
        int[][] a = {{1, 2, 5}, {1, 3, 6}, {2, 3, 1}};
        int k = 3;
        System.out.println(minimumCost(k, a));
    }
}

class UnionSet {

    private int limit;

    private int[] parent;

    private int[] size;

    public UnionSet(int limit) {
        this.limit = limit;
        this.parent = new int[limit + 1];
        this.size = new int[limit + 1];
        this.init();
    }

    public void init() {
        for (int i = 1; i <= limit; ++i) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        int root = parent[x];
        while (parent[root] != root) {
            root = parent[root];
        }

        while (x != root) {
            int f = parent[x];
            parent[x] = root;
            x = f;
        }

        return root;
    }

    public void merge(int a, int b) {
        int p1 = find(a);
        int p2 = find(b);
        if (p1 == p2) {
            return;
        }

        if (size[p1] >= size[p2]) {
            parent[p2] = p1;
            size[p1] = size[p1] + size[p2];
            size[p2] = 0;
        } else {
            parent[p1] = p2;
            size[p2] = size[p1] + size[p2];
            size[p1] = 0;
        }
    }

    public int size() {
        int sum = 0;
        for (int i = 0; i < size.length; ++i) {
            if (size[i] > 0) {
                sum++;
            }
        }
        return sum;
    }
}

class Graph {

    private final Map<Node, Map<Node, Edge>> edgeMap;

    private final Map<Integer, Node> nodeMap;

    private final List<Edge> edges;

    public Graph() {
        this.edgeMap = new HashMap<>();
        this.nodeMap = new HashMap<>();
        this.edges = new ArrayList<>();
    }

    public Map<Integer, Node> getNodeMap() {
        return nodeMap;
    }

    public Node buildNode(int value) {
        Node node = nodeMap.get(value);
        if (node == null) {
            node = new Node(value);
            nodeMap.put(value, node);
        }
        return node;
    }

    public Node getNode(int value) {
        return nodeMap.get(value);
    }

    public Edge buildEdge(Node from, Node to, int weight) {
        Map<Node, Edge> fromEdgeMap = edgeMap.computeIfAbsent(from, k -> new HashMap<>());
        Edge edge = fromEdgeMap.get(to);
        if (edge == null) {
            edge = new Edge(from, to, weight);
            fromEdgeMap.put(to, edge);
            from.out++;
            to.in++;
            from.nexts.add(edge);
            edges.add(edge);
        } else {
            if (edge.weight > weight) {
                edge.weight = weight;
            }
        }
        return edge;
    }

    public Edge addEdge(int from, int to, int weight) {
        return buildEdge(buildNode(from), buildNode(to), weight);
    }

    class Node {
        int value;
        int in;
        int out;
        List<Edge> nexts;

        public Node(int value) {
            this.value = value;
            this.in = 0;
            this.out = 0;
            this.nexts = new ArrayList<>();
        }
    }

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

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

        public int getWeight() {
            return weight;
        }
    }

}

脚本宝典总结

以上是脚本宝典为你收集整理的最低成本联通所有城市（Prim）全部内容，希望文章能够帮你解决最低成本联通所有城市（Prim）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。