使用并查集UnionFind和优先队列PriorityQueue实现Kruskal算法

本文主要是介绍使用并查集UnionFind和优先队列PriorityQueue实现Kruskal算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

拿到题目,先看看UnionFind 和 PriorityQueue 怎么实现吧,谁让上课没好好听呢。

Kruskal算法是通过按照权值递增的顺序依次选择图中的边,当边不处于同一连通分量时加入生成树,否则舍去此边选择下一条代价最小的边,直到所有顶点都在同一连通分量上。

1.UnionFind并查集

并查集适用于动态连通性问题,比如说最小生成树时判定两节点是否在同一连通分量中等等。java实现如下:

UnionFind.java


public class UnionFind {
private int [] id; //每个节点组号
private int [] sz; //每个组的大小
private int count ; //联通分量数目

//初始化
public  UnionFind(int N){
count = N;
id = new int[N];
sz = new int[N];
for(int i=0;i<N;i++){
id[i] = i; //初始情况下每个节点的组号就是该节点的序号
sz[i] = 1; //初始时每个组大小都为1
}
}
//返回联通分量数目
public int count(){
return count;
}
//检查是否联通,如果是,返回true
public boolean connected(int p,int q){
return find(q)==find(p);
}
//查找组号,压缩路径,使得树更加扁平化,提高了find的效率
public int find(int p){
while(p != id[p]){ //找到它的根节点
//将p节点的父节点设置为它的爷爷节点
id[p] = id[id[p]];
p = id[p];
}
return p;
}
//组合Weighted Quick-Union
public void union(int p,int q){
int pID = find(p);
int qID = find(q);
//如果在同一组直接返回
if(pID==qID)
return;
//不是就组合,将小树作为大树的子树
else{
if(sz[pID]<sz[qID]){
id[pID] = qID;
sz[qID] += sz[pID];
}
else{
id[qID] = pID;
sz[pID] += sz[qID];
}
count -- ;    //联通分量数目减少1
}
}

}

2.优先队列

用二叉堆实现的优先队列在进行大量数据的插入元素和删除最大、最小元素时效率更高。

PriorityQueue.java



public class PriorityQueue {
public  Segment [] pq = new Segment[40]; //pq 为线段类的一个对象数组
private int N = 0; //队列元素个数

public PriorityQueue(int maxN){ //初始化队列
for(int i= 0; i<maxN+1; i++){
pq[i] = new Segment() ;
}
}

public boolean isEmpty(){
return N==0 ;
}

public int size(){
return N;
}

public void insert(int v,int i,int j){ //插入队列元素,并按递减排序
pq[++N].weight = v;
pq[N].x = i ;
pq[N].y = j ;
swim(N); //上浮操作
}

public int delMin(){ //由于要为最小生成树服务,这里删除的是最小值
int min = pq[1].weight;
exch(1, N--);
pq[N+1].weight = 9999; //防止末尾元素为空,随便指定一个较大值
sink(1);
return min;
}
//小的游上去
private  void swim(int k){
while(k > 1 && pq[k/2].weight > pq[k].weight){
exch(k/2,k);
k = k/2;
}
}
//大的沉下去
private void sink(int k){
while(2*k <= N){
int j = 2*k;
if(j<N && pq[j].weight > pq[j+1].weight)
j++;
if(pq[k].weight < pq[j].weight)
break;
exch(k, j);
k = j ;
}
}

private void exch(int i,int j){ //线段对象交换,开始时我只交换线段的权重,后来修正
Segment temp = pq[i] ;
pq[i] = pq[j] ;
pq[j] = temp;
}
}

3.由于Kruskal算法的操作是以线段权重大小为顺序,我们要操作的对象是线段,所以需要构造一个简单的线段类:

Segment.java

package com.zsx;


public class Segment {
public int weight; //线段的权重
public int x; //线段的两个顶点
public int y;

}


4.总函数:



import java.util.Scanner;


public class Kruskal {
public static void main(String []args){
int N,v,i,j,sum ;
System.out.println("请输入节点数:");
Scanner in = new Scanner(System.in);
N = in.nextInt(); //节点数
UnionFind uf = new UnionFind(N); //创建并查集对象
PriorityQueue weight = new PriorityQueue(N*N); //创建优先队列对象

System.out.println("请输入节点编号及他们之间路径的权重,输入-1结束:");
while((i = in.nextInt())!= -1){ //当输入-1时停止输入
int x=0,y=0;
j = in.nextInt();
v = in.nextInt();
weight.insert(v,i,j); //优先队列中插入节点
}
System.out.println("Kruskal算法构造的最小生成树成功:");
for(i=0,sum=0;i< N -1 ;){ //最小生成树中,N个节点最多有N-1条边
int p = weight.pq[1].x;
int q = weight.pq[1].y;
if(!uf.connected(p,q )){ //按照边的权重从小到大开始选择,当线段的2个节点不在一个连通分量中时选择
System.out.println(weight.pq[1].weight+ " "+p +" "+q );
sum += weight.pq[1].weight;
uf.union(p, q); //标记为一个同分量
i++;
}
weight.delMin();
}
System.out.println("权重和:"+sum);

}
}

这篇关于使用并查集UnionFind和优先队列PriorityQueue实现Kruskal算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1023409

相关文章

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT?二、JWT 基本结构

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Android实现两台手机屏幕共享和远程控制功能

《Android实现两台手机屏幕共享和远程控制功能》在远程协助、在线教学、技术支持等多种场景下,实时获得另一部移动设备的屏幕画面,并对其进行操作,具有极高的应用价值,本项目旨在实现两台Android手... 目录一、项目概述二、相关知识2.1 MediaProjection API2.2 Socket 网络

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Maven的使用和配置国内源的保姆级教程

《Maven的使用和配置国内源的保姆级教程》Maven是⼀个项目管理工具,基于POM(ProjectObjectModel,项目对象模型)的概念,Maven可以通过一小段描述信息来管理项目的构建,报告... 目录1. 什么是Maven?2.创建⼀个Maven项目3.Maven 核心功能4.使用Maven H

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

C# Where 泛型约束的实现

《C#Where泛型约束的实现》本文主要介绍了C#Where泛型约束的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录使用的对象约束分类where T : structwhere T : classwhere T : ne

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

将Java程序打包成EXE文件的实现方式

《将Java程序打包成EXE文件的实现方式》:本文主要介绍将Java程序打包成EXE文件的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录如何将Java程序编程打包成EXE文件1.准备Java程序2.生成JAR包3.选择并安装打包工具4.配置Launch4

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr