使用并查集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

相关文章

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

go中空接口的具体使用

《go中空接口的具体使用》空接口是一种特殊的接口类型,它不包含任何方法,本文主要介绍了go中空接口的具体使用,具有一定的参考价值,感兴趣的可以了解一下... 目录接口-空接口1. 什么是空接口?2. 如何使用空接口?第一,第二,第三,3. 空接口几个要注意的坑坑1:坑2:坑3:接口-空接口1. 什么是空接

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专