最小生成树之Kruskal

CSDN

package com.zhang.reflection.面试.算法模版.图.最小生成树;
import java.util.*;
/**
 * 要求无向图，生成最小生成树，以边的角度出发，依次选择最小的边，判断这条边加上会不会形成环，不会就加上，会就不加了
 * 判断会不会形成环需要用到并查集。
 */
public class Kruskal {
    //图
    static class Graph{
        //点集<编号，实际的点>
        public HashMap<Integer, Node> nodes;
        //边集
        public HashSet<Edge> edges;
        public Graph(){
            nodes=new HashMap<>();
            edges=new HashSet<>();
        }
    }
    //点
    static class Node{
        //点上的值
        public int value;
        //点的入度
        public int in;
        //点的出度
        public int out;
        //相邻节点集,以该节点为起点
        public ArrayList<Node> nexts;
        //相邻边集，以该节点为起点
        public ArrayList<Edge> edges;
        public Node(int value){
            this.value=value;
            in=0;
            out=0;
            nexts=new ArrayList<>();
            edges=new ArrayList<>();
        }
    }
    //边
    static class Edge{
        //边得权值
        public int weight;
        //边的起点
        public Node from;
        //边的终点
        public Node to;
        public Edge(int weight, Node from, Node to){
            this.weight=weight;
            this.from=from;
            this.to=to;
        }
    }
    //简化版并查集
    //isSameSet和unionSet接口
    private static class Myset {
        public HashMap<Node, List<Node>> setMap;

        public Myset(Collection<Node> nodes) {
            for (Node node : nodes) {
                List<Node> list = new ArrayList<>();
                list.add(node);
                setMap.put(node, list);
            }
        }
        //from和to是否在同一个集合里面
        public boolean isSameSet(Node from, Node to) {
            List<Node> fromNode = setMap.get(from);
            List<Node> toNode = setMap.get(to);
            //内存地址相同就是同一个集合，否则就不是同一个集合
            return fromNode == toNode;
        }
        //合并两个集合
        public void unionSet(Node from, Node to) {
            List<Node> fSet = setMap.get(from);
            List<Node> tSet = setMap.get(to);
            for (Node node : tSet) {
                fSet.add(node);
                setMap.put(node, fSet);
            }
        }
    }
    //比较器
    public static class EdgeCompator implements Comparator<Edge> {
        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    }
    //克鲁斯卡尔算法
    public static Set<Edge> kruskalMST(Graph graph) {
        Myset myset = new Myset(graph.nodes.values());
        //用小堆逐渐加入边
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeCompator());
        priorityQueue.addAll(graph.edges);
        Set<Edge> res = new HashSet<>();
        while (!priorityQueue.isEmpty()) {
            Edge poll = priorityQueue.poll();
            //并查集避免环路
            if (!myset.isSameSet(poll.from, poll.to)) {
                res.add(poll);
                myset.unionSet(poll.from, poll.to);
            }
        }
        return res;
    }
}