《算法》unionfind算法及改进

2023-12-22 12:32
文章标签 算法 改进 unionfind

本文主要是介绍《算法》unionfind算法及改进，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法详细内容参考《算法》第4版1.5案例研究：union-find算法

分析运行结果：

package union;
import java.util.Arrays;
import java.util.Random;class WeightQuickUnion {private int[] id;	//分量id,每个节点所属集合标识private int[] size; //以该节点为根其分量大小private int count;	//分量数量//initializepublic WeightQuickUnion(int N){count = N;	//初始化每个节点都是一个分量，union时减少countid = new int[N];for(int i = 0; i < N; ++i){id[i] = i;}size = new int[N];for(int i = 0; i < N; ++i){size[i] = 1;}}public int count(){return count;}public boolean connected(int left, int right){return find(left) == find(right);}//O(logN) time 返回节点所属集合标识public int find(int node){while(node != id[node]){node = id[node];}return node;}public void find_quick_union(int left, int right){int left_id = find(left);int right_id = find(right);if(left_id != right_id){if(size[left_id] < size[right_id]){id[left_id] = right_id;size[left_id] += size[right_id];}else{id[right_id] = left_id;size[right_id] += size[left_id];}--count;}return ;}
}class WeightQuickCompressUnion {private int[] id;	//分量id,每个节点所属集合标识private int[] size; //以该节点为根其分量大小private int count;	//分量数量//initializepublic WeightQuickCompressUnion(int N){count = N;	//初始化每个节点都是一个分量，union时减少countid = new int[N];for(int i = 0; i < N; ++i){id[i] = i;}size = new int[N];for(int i = 0; i < N; ++i){size[i] = 1;}}public int count(){return count;}public boolean connected(int left, int right){return find(left) == find(right);}//O(logN) time 返回节点所属集合标识public int find(int node){int root = node;while(root != id[root]){root = id[root];}while(node != root){node = id[node];id[node] = root;}return root;}public void find_quick_union(int left, int right){int left_id = find(left);int right_id = find(right);if(left_id != right_id){if(size[left_id] < size[right_id]){id[left_id] = right_id;size[left_id] += size[right_id];}else{id[right_id] = left_id;size[right_id] += size[left_id];}--count;}return ;}
}final class StdRandom {private static Random random;    // pseudo-random number generatorprivate static long seed;        // pseudo-random number generator seed// static initializerstatic {// this is how the seed was set in Java 1.4seed = System.currentTimeMillis();random = new Random(seed);}// don't instantiateprivate StdRandom() { }/*** Sets the seed of the pseudorandom number generator.* This method enables you to produce the same sequence of "random"* number for each execution of the program.* Ordinarily, you should call this method at most once per program.** @param s the seed*/public static void setSeed(long s) {seed   = s;random = new Random(seed);}/*** Returns the seed of the pseudorandom number generator.** @return the seed*/public static long getSeed() {return seed;}/*** Returns a random real number uniformly in [0, 1).* @return a random real number uniformly in [0, 1)*/public static double uniform() {return random.nextDouble();}/*** Returns a random integer uniformly in [0, n).* * @param n number of possible integers* @return a random integer uniformly between 0 (inclusive) and {@code n} (exclusive)* @throws IllegalArgumentException if {@code n <= 0}*/public static int uniform(int n) {if (n <= 0) throw new IllegalArgumentException("argument must be positive");return random.nextInt(n);}}public class Union {private int[] id;	//分量id,每个节点所属集合标识private int count;	//分量数量//initializepublic Union(int N){count = N;	//初始化每个节点都是一个分量，union时减少countid = new int[N];for(int i = 0; i < N; ++i){id[i] = i;}}public boolean quick_find_connected(int left, int right){return quick_find(left) == quick_find(right);}public boolean find_connected(int left, int right){return find(left) == find(right);}//O(1) timepublic int quick_find(int node){return id[node];}//O(n^2) time to union if union N timespublic void quick_find_union(int left, int right){int left_id = quick_find(left);     //O(1) time to findint right_id = quick_find(right);if(left_id != right_id){for(int node = 0; node < id.length; ++node){if(quick_find(node) == left_id){id[node] = right_id;}}--count;}return ;}//O(logN) time 返回节点所属集合标识public int find(int node){while(node != id[node]){node = id[node];}return node;}//O(N*treeHeight) time if union N timespublic void find_lazy_quick_union(int left, int right){int left_id = find(left);int right_id = find(right);if(left_id != right_id){id[left_id] = right_id;--count;}return ;}public static void main(String[] args) {// TODO Auto-generated method stubfinal int E = 90000;final int N = 100000;int[][] eadges = new int [E][2];for(int i = 0; i < E; ++i){eadges[i][0] = StdRandom.uniform(N);eadges[i][1] = StdRandom.uniform(N);}
//		System.out.println(Arrays.deepToString(eadges));long startTime;long endTime;System.out.println("Union");Union UF =  new Union(N);startTime = System.currentTimeMillis();for(int i = 0; i < E; ++i){UF.quick_find_union(eadges[i][0], eadges[i][1]);}endTime = System.currentTimeMillis();System.out.println("Run Time："+(endTime-startTime)+"ms");/*for(int p = 0; p < N; ++p){for(int q = 0; q < N; ++q)System.out.print(UF.quick_find_connected(p,q)+" ");}*/
//		System.out.println("");System.out.println(UF.count);System.out.println("LazyWeight");Union LazyUF = new Union(N);startTime = System.currentTimeMillis();for(int i = 0; i < E; ++i){LazyUF.find_lazy_quick_union(eadges[i][0], eadges[i][1]);}endTime = System.currentTimeMillis();System.out.println("Run Time："+(endTime-startTime)+"ms");/*for(int p = 0; p < N; ++p){for(int q = 0; q < N; ++q)System.out.print(LazyUF.find_connected(p,q)+" ");}*/
//		System.out.println("");System.out.println(LazyUF.count);System.out.println("Weight");WeightQuickUnion WQUF = new WeightQuickUnion(N);startTime = System.currentTimeMillis();for(int i = 0; i < E; ++i){WQUF.find_quick_union(eadges[i][0], eadges[i][1]);}endTime = System.currentTimeMillis();System.out.println("Run Time："+(endTime-startTime)+"ms");/*for(int p = 0; p < N; ++p){for(int q = 0; q < N; ++q)System.out.print(WQUF.connected(p, q)+" ");}*/
//		System.out.println("");System.out.println(WQUF.count());System.out.println("Weight & Compress");WeightQuickCompressUnion WCUF = new WeightQuickCompressUnion(N);startTime = System.currentTimeMillis();for(int i = 0; i < E; ++i){WCUF.find_quick_union(eadges[i][0], eadges[i][1]);}endTime = System.currentTimeMillis();System.out.println("Run Time："+(endTime-startTime)+"ms");/*for(int p = 0; p < N; ++p){for(int q = 0; q < N; ++q)System.out.print(WCUF.connected(p, q)+" ");}*/
//		System.out.println("");System.out.println(WCUF.count());}
}

打印出来的结果： 

Union
Run Time：5248ms
20303
LazyWeight
Run Time：739ms
20303
Weight
Run Time：736ms
20303
Weight & Compress
Run Time：19ms
20303
调大边数E 

final int E = 99000;
final int N = 100000;

Union
Run Time：6076ms
16619
LazyWeight
Run Time：1296ms
16619
Weight
Run Time：1271ms
16619
Weight & Compress
Run Time：19ms
16619
调小边数E 

final int E = 1000;
final int N = 100000;


Union
Run Time：43ms
99000
LazyWeight
Run Time：0ms
99000
Weight
Run Time：1ms
99000
Weight & Compress
Run Time：0ms
99000

union、LazyWeight、Weight、Weight & Compress对应教材quick-find、quick-union、加权quick-union、路径压缩的加权quick-union算法。

边数比较小时图比较稀疏，输出结果中99000表示一共99000个分量，而总共节点为100000，quick-union中每棵树高度都不大所以运行起来比加权quick-union更快，因为quick-union中多了求树节点数量、将小树指向大树的步骤。而增大边数时加权quick-union效果比quick-union更好，因为加权quick-union可以保证树高度最多为logN,N为节点数。

挺有用的结论，把小树的根指向大树的根可以保证树高度小于logN，证明：


小树节点总数N1，高度为h1，大树节点总数N2，高度为h2,；将小树根指向大树根节点会造成小树节点高度加1

h1+1 <= log N1 + 1 = log(N1+N1) <= log(N1 + N2)

大树节点高度不变

所以合并之后的树高度不大于log(N1 + N2)

又单个节点高度为0，数学归纳法即知

这篇关于《算法》unionfind算法及改进的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/523951。

相关文章

SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2