图-最小生成树-Kruskal算法

2022-4-14 diaba 算法 

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

« 图-最小生成树-Prim算法 | 算法-图-深度优先遍历»

发表评论：

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