题解 | #最小生成树#

public class Solution {
    /**
     * 存图的边
     */
    private static ArrayList<Edge> list = new ArrayList<>();
    /**
     * 存图的节点
     */
    private static HashMap<Integer, EdgeNode> nodeMap = new HashMap<>();
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        Solution t = new Solution();
        for (int i = 0; i < cost.length; i++) {
            int[] edge = cost[i];
            t.createGraph(edge[0],edge[1],edge[2]);
        }
        return getMiniTree();
    }
    
    /**
     * 构件图
     * @param node1
     * @param node2
     * @param weight
     */
    public void createGraph(int node1, int node2, int weight) {
        // 如果点不存在,则新构建一个点,如果存在就使用存在的点
        EdgeNode edgeNode1 = nodeMap.get(node1);
        EdgeNode edgeNode2 = nodeMap.get(node2);
        if(edgeNode1 == null){
            edgeNode1 = new EdgeNode(node1);
            nodeMap.put(node1,edgeNode1);
        }
        if(edgeNode2 == null){
            edgeNode2 = new EdgeNode(node2);
            nodeMap.put(node2,edgeNode2);
        }

        Edge edge = new Edge(edgeNode1,edgeNode2,weight);
        list.add(edge);
    }

    public Integer getMiniTree() {
        // 将图中的所有边按权重从小到大排序
        list.sort(Comparator.comparingInt(Edge::getWeight));
        Map<Integer,Integer> nodeMap = new HashMap<>(16);
        int result = 0;
        Integer nodeName1,nodeName2;
        for (int i = 0,j = 1; i < list.size(); i++) {
            nodeName1 = find(nodeMap,list.get(i).getEdgeNode1().getNodeName());
            nodeName2 = find(nodeMap,list.get(i).getEdgeNode2().getNodeName());
            if(!nodeName1.equals(nodeName2)){
                // 两个点不相等,记录这一条边
                nodeMap.put(nodeName1,nodeName2);
                result += list.get(i).getWeight();
            }
        }
        return result;
    }

    /**
     * 该方法用于判断两个结点连接后是否会形成环
     * @param map 已经遍历过的节点集合
     * @param nodeName 将要遍历的节点名称
     * @return
     */
    private Integer find(Map<Integer, Integer> map, Integer nodeName) {
        // 循环直到没有遍历过的点
        while(map.get(nodeName) != null){
            nodeName = map.get(nodeName);
        }
        return nodeName;
    }
}

class Edge {
    private EdgeNode edgeNode1;
    private EdgeNode edgeNode2;
    private int weight;

    public Edge(EdgeNode edgeNode1, EdgeNode edgeNode2, int weight) {
        this.edgeNode1 = edgeNode1;
        this.edgeNode2 = edgeNode2;
        this.weight = weight;
    }

    public EdgeNode getEdgeNode1() {
        return edgeNode1;
    }

    public void setEdgeNode1(EdgeNode edgeNode1) {
        this.edgeNode1 = edgeNode1;
    }

    public EdgeNode getEdgeNode2() {
        return edgeNode2;
    }

    public void setEdgeNode2(EdgeNode edgeNode2) {
        this.edgeNode2 = edgeNode2;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }
}

class EdgeNode {
    private Integer nodeName;

    public Integer getNodeName() {
        return nodeName;
    }

    public void setNodeName(Integer nodeName) {
        this.nodeName = nodeName;
    }

    public EdgeNode(Integer nodeName) {
        this.nodeName = nodeName;
    }
}