package com.jiucaiyuan.net.algrithm.graph;



import com.jiucaiyuan.net.algrithm.set.UnionFindSet;



import java.util.*;



/**

 * 图的Kruskal排序算法（k算法）

 * 适用于：无向图；

 * 作用：生成最小生成树

 * 最小生成树：保障节点连通性的同时权值总合最小

 * 思路：边权值排序，从小到大逐个增加，是否行程环，如果形成环，不要，如果未生成，继续，直到所有的边处理完毕（用到并查集）

 * 是否形成环判断：这个边链接的两个节点是否在同一个集合里，如果不在一个集合里，加上这条边，肯定不会行成环

 * @Author jiucaiyuan  2022/4/14 19:38

 * @mail services@jiucaiyuan.net

 */



public class Kruskal {



    /**

     * 生成无向图graph的最小生成树

     * 保持各个节点连通性，且保留边的权重和最小

     * @param graph 无向图

     * @return 最小生成树中包含保留的边

     */

    public static Set<Edge> kruskalMTS(Graph graph){

        UnionFindSet unionFindSet = new UnionFindSet((List)graph.nodes.values());

        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new Comparator<Edge>(){

            @Override

            public int compare(Edge o1, Edge o2) {

                return o1.weight - o2.weight;

            }

        });

        for(Edge edge:graph.edges){

            priorityQueue.add(edge);  //O(logN)

        }

        Set<Edge> result = new HashSet<>();

        while (!priorityQueue.isEmpty()){

            Edge edge = priorityQueue.poll();  //O(logN)

            //如果当前边两端节点不在同一个集合，则保留该边，合并两遍的集合

            if(!unionFindSet.isSameSet(edge.from,edge.to)){

                result.add(edge);

                unionFindSet.union(edge.from,edge.to);

            }

        }

        return result;

    }

}