1. 查找-合并算法
查找:检查两个对象是否属于同一个集合
合并:用一个集合替代两个对象分别对应的集合。
1.1. 快速查找
数据结构:使用一个大小为N的数组id[],p和q是连通的如果他们对应的id值一样。
例如:
节点: i 0 1 2 3 4 5 6 7 8 9
初始: id[i] 0 1 2 3 4 5 6 7 8 9
当前值:id[i] 0 1 9 9 9 6 6 7 8 9
根据当前值,可以看出0是一个集合,1是一个集合,2,3,4,9属于一个集合,5,6属于一个集合,7是一个集合,8是一个集合。
可以看出,5,6是连通的,2,3,4,9是连通的。
问题:节点3,6连通么?
查找操作:因为id[3]=9;id[6]=6,不相同,所以3,6是非连通的。
合并操作:对3,6节点对,.把所有和id[3]相同的id数组里元素值设为id[6].
结果:
i 0 1 2 3 4 5 6 7 8 9
id[i] 0 1 6 6 6 6 6 7 8 6
快速查找的方法:查找可在线性时间内完成,但是合并操作需要O(N)操作
因此,若执行M对节点的连通性的检查,需要O(MN)的操作。
1.2 快速合并
数据结构:使用一个大小为N的数组id[],id[i]表示的是节点i的父节点,节点i的根节点是id[id[id[…id[i]…]]],直到值不变,其实,每一个根节点都是自连接的,即id[i]=i。
例如:
节点: i 0 1 2 3 4 5 6 7 8 9
初始: id[i] 0 1 2 3 4 5 6 7 8 9
当前值:id[i] 0 1 9 4 9 6 6 7 8 9
例如,根据当前值可以看出,3的根节点是9,5的根节点是6
查找操作:就是检查p和q的根节点是否相同,因此,3,5是不连通的。
合并操作:为了合并p和q分别所在的集合,设置节点p的根节点的id值为q节点的根节点。
例如:
i 0 1 2 3 4 5 6 7 8 9
id[i] 0 1 9 4 9 6 6 7 8 6
快速合并的方法:查找可能最坏情况下需要O(N)操作
合并操作,只需要常数操作。
总的来说:执行M对N个节点的查找合并操作,需要O(MN)时间。
1.3 改进操作啊
在快速合并的基础上改进。因为快速合并仅仅是把一个节点的根设置为另一个节点的根。这样构成的树可能就比较高(极端情况是一个线性表的形式),因此,要设法减少树的高度,其实很简单,在合并的时候,把树的数目小的合并到数目大的上去就可以了。因此,需要增加一个数组sz来记录这个节点为根的树的大小。
查找操作:和快速合并一样。
合并操作:把小树合并到大树,更新sz数组相应的元素。
部分代码:
int i=root(p),j=root(q);
if(sz[i]<sz[j]) {id[i]=j;sz[j]+=sz[i]};
else {id[j]=I;sz[i]+=sz[j]};
改进的操作:查找操作O(lgN)时间可以;合并操作O(1);
总的来说:执行M对N个节点的查找合并操作,需要O(MlgN)时间。
还可以继续改进:路径压缩。在快速合并的基础上采用路径合并,即再查找p节点的过程中,把相应的路径上的节点的父节点设置为root(p)。一种简单的替换是仅仅把父节点设置为它的祖父节点就可以。
public int root(int i){
while(i!=id[i]){
id[i]=id[id[i]];
i=id[i];
}
return i;
}
改进2需要的操作:O(MlgN),实际过程中,是线性的,因为lgN是个常数。
1.4 应用
1)网络连通性的检查;
2)Kruskal’s的最小生成树算法。
分享到:
相关推荐
研究生计算机算法上机作业,总共有15个最常用的算法,比如背包算法等。并含有运行结果。
基于Bloom Filter的虚拟路由合并与查找算法的研究,梁飞,徐明伟,当前,随着网络虚拟化的发展,对虚拟路由器的研究也成为热点。通常有多个虚拟路由器部署在一台物理路由器上,导致路由表的增加,
很好地算法设计资料,你值得拥有哦,里面各种算法设计很详细的哦。
二分查找算法是运用分治的典型例子:给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。所以容易设计出二分搜索算法:在 a[0] [1] [n-1] 中搜索 x, 找到x时返回其在数组中的位置,否则返回-...
求最小支撑树的克鲁斯卡尔算法//用于低秩合并算法//边数i++){ //把所有的边保存在E中//下面是采用路径压缩的方法查找元素://查找//按秩合并//合并/
两阶段合并聚类算法java数据挖掘算法源码.rar 数据挖掘算法是根据数据创建数据挖掘模型的一组试探法和计算。 为了创建模型,算法将首先分析您提供的数据,并查找特定类型的模式和趋势。概念描述算法使用此分析的结果...
- 最大和最小堆、优先队列、Trie、树、二叉搜索树、AVL树、红黑树、区段树 - 包含最小/最大/总和范围查询示例、Fenwick Tree(二叉索引树)、图形(有向和无向)、 Disjoint Set - 并集-查找数据结构或合并-查找集、...
最近对和凸包问题的蛮力算法、深度优先查找和广度优先查找 第4章 插入排序、拓扑排序、计算中值和选择问题 第5章 合并排序、快速排序、大整数乘法 第6章 平衡查找树、堆的概念、堆排序 第8章 最优二叉查找树、...
与CABDDCC算法相反,最后是通过对小簇集合的合并,形成最终的结果,在第一阶段主要是通过K近邻的思想形成小规模的连通图,第二阶段通过RI(相对互连性)和RC(相对近似性)来选一个最佳的簇进行合并。详细介绍链接 ...
02-003单链表的创建与操作、加工型操作、单链表合并 03-001栈的定义与应用、循环链表的定义与操作 03-002栈的应用、数制转换、括号匹配、行编辑问题、迷宫问题 03-003栈的应用:表达式求值、后缀表达式的表示 03-...
printf("\t*************选择排序实验报告****************\n");...合并排序 <*******\n"); printf("\t***********> 9.结束程序 <*******\n"); printf("\t*********************************************\n");
西安电子科技大学《算法设计与分析》上机题。渗透问题(Percolation) 使用合并-查找(union-find)数据结构,编写程序通过蒙特卡罗模拟(Monte Carlo simulation)来估计渗透阈值的值。
C常用算法:有常用的选择法冒泡法合并法顺序查找等
#编程练习##For 算法:设计与分析,第 1 部分(Tim Roughgarden 教授) ###1:InversionCounter 应用分治递归算法(基于合并排序)来计算未排序数组中的反转。 ###2:QuickSorter 使用 QuickSort 对数组进行排序,并...
1、选择顺序或链式存储结构实现线性表的基本操作 2、采用顺序或链式存储方式存储线性表,在此基础上实现线性表的各个操作,以及线性表的合并操作
算法 数组 二分查找 - , 找到最大滑动窗口 - 搜索旋转数组 - 找到最小的公数 - 旋转阵列 - 查找低/高指数 - 向左移动零 - 找到最大单笔卖出利润 - 实施快速排序 - 合并重叠区间 - 两个值之和 - , 链表 反转单向链表 ...
本书旨在探讨如何优化算法效率,详细阐述了经典算法和特殊算法的实现、应用技巧和复杂度验证过程,内容由浅入深,能帮助读者快速掌握复杂度适当、正确率高的高效编程方法以及自检、自测技巧,是参加ACM ICPC、Google...
链表 双链表 队列 叠 哈希表 堆 - 最大和最小堆版本 优先队列 Trie 树 二叉搜索树 ...区段树 - 包含最小/最大/...Disjoint Set - 并集 - 查找数据结构或合并 - 查找集 绽放过滤器 LRU 缓存 - 最近最少使用 (LRU) 缓存
合并排序(完成): 后缀数组:, , , , Knuth-Morris-Pratt 算法 (KMP): , ,, Rabin-Karp 算法: , , 尝试: , , , , , 图的深度优先遍历: , , , 图的广度优先遍历: , , , Dijkstra 算法: , , , , 二叉索引树: ...