package com.jiucaiyuan.net.algrithm.graph;



import java.util.Comparator;

import java.util.HashSet;

import java.util.PriorityQueue;

import java.util.Set;



/**

 * 图的Prim排序算法（p算法）

 * 适用于：无向图；

 * 作用：生成最小生成树

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

 * 思路：解锁最小的边，相邻的节点是解锁的节点，再找相邻的边，从解锁的边中找最小权重的边（这个边两个节点必有不在解锁节点中）

 *

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

 * @mail services@jiucaiyuan.net

 */



public class Prim {



    /**

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

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

     *

     * @param graph 无向图

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

     */

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

        //解锁的边进入小跟堆

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

            @Override

            public int compare(Edge o1, Edge o2) {

                return o1.weight - o2.weight;

            }

        });

        //已经处理的节点放到set中

        HashSet<Node> set = new HashSet<>();

        //最小生成树包含的边

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



        for (Node node : graph.nodes.values()) {  //如果图中存在不连通的图需要这个循环（森林）



            //node是开始节点

            if (set.contains(node)) {

                set.add(node);

                //有一个点开始，解锁所有相邻的边

                for (Edge edge : node.edges) {

                    priorityQueue.add(edge);

                }

                while (!priorityQueue.isEmpty()) {

                    Edge edge = priorityQueue.poll(); //弹出所有解锁的边中最小的边

                    Node toNode = edge.to; //可能的一个新节点

                    if (!set.contains(toNode)) {//不含有的时候，就是新节点

                        set.add(toNode);

                        for (Edge nextEdge : toNode.edges) {  //有可能重复放边，不过会检查新节点，不影响

                            priorityQueue.add(nextEdge);

                        }



                    }

                }

            }

            //end

        }

        return result;

    }

}