图-最小生成树-Prim算法

2022-4-14 diaba 算法 

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

« 图-最短路径-Dijkstra算法 | 图-最小生成树-Kruskal算法»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022