最低成本联通所有城市（Kruskal）

本文主要是介绍最低成本联通所有城市（Kruskal），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

想象一下你是个城市基建规划者，地图上有 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（eloge）

import java.util.*;

public class Solution {
    public static int minimumCost(int n, int[][] connections) {
        Graph graph = new Graph();
        Union union = new Union(n);
        for (int i = 0; i < connections.length; ++i) {
            graph.addEdge(connections[i][0], connections[i][1], connections[i][2]);

        }
        List<Edge> edges = graph.getEdges();
        PriorityQueue<Edge> queue = new PriorityQueue<Edge>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
        queue.addAll(edges);
        Set<Edge> resSet = new HashSet<Edge>();
        while (!queue.isEmpty()) {
            Edge edge = queue.poll();
            if (!union.inSameSet(edge.from.value, edge.to.value)) {
                resSet.add(edge);
                union.union(edge.from.value, edge.to.value);
            }
        }
        if (union.size() != 1) {
            return -1;
        } else {
            return resSet.stream().mapToInt(edge -> edge.weight).sum();
        }
    }

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

class Graph {

    private Map<Node, Map<Node, Edge>> edgeMap = new HashMap<>();

    private Map<Integer, Node> nodes = new HashMap<>();

    private List<Edge> edges = new ArrayList<>();

    public List<Edge> getEdges() {
        return edges;
    }

    public Map<Integer, Node> getNodes() {
        return nodes;
    }

    /**
     * 如果边不存在，则创建边，同时保留最优边
     *
     * @param from
     * @param to
     * @param weight
     * @return
     */
    private Edge buildEdge(Node from, Node to, int weight) {
        Map<Node, Edge> fromMap = edgeMap.computeIfAbsent(from, k -> new HashMap<>());
        Edge edge = fromMap.get(to);
        // 新边
        if (edge == null) {
            edge = new Edge(from, to, weight);
            fromMap.put(to, edge);
            from.edges.add(edge);
            edges.add(edge);
        } else {
            // 留下最优边
            if (edge.weight > weight) {
                edge.weight = weight;
            }
        }
        return edge;
    }

    /**
     * 如果不存在，则创建节点
     *
     * @param index
     * @return
     */
    private Node buildNode(int index) {
        Node node = nodes.get(index);
        if (node == null) {
            node = new Node(index);
            nodes.put(index, node);
        }
        return node;
    }

    /**
     * 添加边
     *
     * @param fromIndex
     * @param toIndex
     * @param weight
     */
    public void addEdge(int fromIndex, int toIndex, int weight) {
        buildEdge(buildNode(fromIndex), buildNode(toIndex), weight);
    }
}

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;
    }
}

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

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

class Union {
    private int[] parent;
    private int[] size;

    public Union(int n) {
        this.parent = new int[n + 1];
        this.size = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        int p = parent[x];
        if (p == x) {
            return p;
        }
        p = find(p);
        parent[x] = p;
        return p;
    }

    public void union(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 boolean inSameSet(int a, int b) {
        return find(a) == find(b);
    }

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

这篇关于最低成本联通所有城市（Kruskal）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！