当前位置:首页 >> 理学 >>

Ch08-不相交集_图文

不相交集
高文宇 gwyy@163.com

§1 等价关系
? 定义1(关系):relation R is defined on a set S if for every pair of elements (a, b), a, b ?S, a R b is either true or false. If a R b is true, then we say that a is related to b. ? 定义2(等价关系):A relation, ~, over a set, S, is said to be an equivalence relation over S iff it is symmetric, reflexive, and transitive over S. ? 定义3(等价类):Two members x and y of a set S are said to be in the same equivalence class iff x ~ y.

§2 动态等价性问题

动态连通性问题
? 问题的输入是一系列整数对,其中每个整数表示 某种类型的对象,一个整数对(p, q)可以视为“p 和q是相连的”,“相连”是等价关系。 ? 程序从输入中读取整数对(p, q),如果已知前面所 有的整数对都不能说明p和q是相连的,那么将这 一对整数对写入到输出中。如果已知的数据可以 说明p和q是相连的,则程序忽略该整数对,并继 续处理下一个整数对。

Union Find
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Given a set of N objects. ? Union command: connect two objects. ? Find/connected query: is there a path connecting the two objects? Dynamic connectivity union(4, 3) union(3, 8) union(6, 5) union(9, 4) union(2, 1) connected(0, 7)--No connected(8, 9)--Yes union(5, 0) union(7, 2) connected(0, 7)--Yes union(1, 0) union(6, 1)

动态连通性问题的几个难点
? ? ? ? 对象的个数 N 可能会很庞大 操作的次数(find,union)M 可能很庞大 Find 查询和 union操作可能是交替进行的 算法是动态的,集合(等价类)会因为 union操作而发生改变。 ? 算法是联机算法(on-line)。

Union-find的基本实现
? Union-find
typedef int DisjSet[ NumSets + 1 ]; typedef int SetType; typedef int ElementType; void Initialize( DisjSet S ) { int i; for( i = NumSets; i > 0; i-- ) S[ i ] = i; } void SetUnion( DisjSet S, SetType Root1, SetType Root2 ) int r1 = find(Root1); int r2 = find(Root2); if (r1 == r2) return; for (int i = 1; i <= NumSets; i++) if (S[ i ] == r1) S[ i ] = r2; } SetType Find( ElementType X, DisjSet S ) { return S[ X ]; }

{

Union-find示例
S[ i ] 1 初始 1 4,3 3,8 6,5 9,4 2,1 1 1 2 2 3 3 3 8 8 8 8 4 4 3 8 8 8 8 5 5 6 6 7 7 8 8 8 8 8 8 9 9

5 5 5

5 5 5

8 8

算法分析
? ? ? ? find()方法:O(1) union()方法:O(N) connected():O(1) 因此,若有N个节点,输入为N个整数对, 则总的运行时间为O(N^2)。 ? 对于有100万个节点,200万个整数对的测 试文件largeUF.txt来说,Quick-find无能为 力。

采用树形结构实现union
? 通过采用“树”结构来加速union操作
typedef int DisjSet[ NumSets + 1 ]; typedef int SetType; typedef int ElementType; void Initialize( DisjSet S ) { int i; for( i = NumSets; i > 0; i-- ) S[ i ] = 0; } void SetUnion( DisjSet S, SetType Root1, SetType Root2 ) //Root1和Root2分别为两棵树的根节点 S[ Root2 ] = Root1; } SetType Find( ElementType X, DisjSet S ) { if( S[ X ] <= 0 ) return X; else return Find( S[ X ], S ); }

{

Quick Union
? Quick Union使用例程
Algorithm: { /* step 1: read the relations in */ Initialize N disjoint sets; while ( read in a ~ b ) { if ( ! (Find(a) == Find(b)) ) SetUnion( Find( i ), Find( j ) ); } /* end-while */ /* step 2: decide if a ~ b */ while ( read in a and b ) if ( Find(a) == Find(b) ) output( true ); else output( false ); }

Quick union 示例

Quick union算法分析
? ? ? ? find()方法:增加了 union()方法:O(1),但union依赖于find connected():不变 问题在于quick union算法在最坏情况下并 不比quick find算法好。

加权quick union算法
? Union-by-Size:简单修改quick union算法 就能大幅提高性能。与其在union()中随意 地将一棵树连接到另一棵树,我们可以记 录每一棵树的大小,并总是将较小的树连 接到较大的树上。
? Union-by-Height: Always change the shallow tree

Union by size实际效果
? 命题H:对于N个节点,加权quick-union算 法构造的森林中的任意节点的深度不超过 lgN。 ? 推论:对于加权quick-union算法和N个节点, 在最坏情况下find(),connected(),union() 的成本的增长数量级为lgN。

Union by height
typedef int DisjSet[ NumSets + 1 ]; typedef int SetType; typedef int ElementType; void Initialize( DisjSet S ) { int i; for( i = NumSets; i > 0; i-- ) S[ i ] = 0; } void SetUnion( DisjSet S, SetType Root1, SetType Root2 ) { //Root1和Root2分别为两棵树的根节点 if( S[ Root2 ] < S[ Root1 ] ) /* Root2 is deeper set */ S[ Root1 ] = Root2; /* Make Root2 new root */ else { if( S[ Root1 ] == S[ Root2 ] ) /* Same height, */ S[ Root1 ]--; /* so update 用负数表示树的高度*/ S[ Root2 ] = Root1; } }

进一步改进--路径压缩
? 理想情况下,我们希望每个节点都直接连接在它的根节点 上,但我们又不希望像quick-find算法中那样通过修改大 量链接来做到这一点。 ? 但是接近这种理想状态的方法很简单,那就是在检查节点 的同时将它们直接连接到根节点。 ? 要实现路径压缩,只需在find()方法中稍做修改即可。
SetType Find ( ElementType X, DisjSet S ) { if ( S[ X ] <= 0 ) return X; else return S[ X ] = Find( S[ X ], S ); }

作业
? 看程序: ? disjsets.c—不相交集的实现

再见

? 再见


相关文章:
Ch08-不相交集_图文.ppt
Ch08-不相交集 - 数据结构课件,使用教材“数据结构与算法分析-C语言描述”
CH08-队列解析_图文.ppt
CH08-队列解析 - 队列 主要内容 ? ? ? 队列介绍 队列的抽象定义 队
ch08-数组_图文.ppt
ch08-数组 - 第8章:数组 第8章 数组 1 第8章:数组 本章要点 ?
ch08-Approaches to System Development_图文.ppt
ch08-Approaches to System Development_生物
GNSS-PA-Ch08-pp38_图文.ppt
GNSS-PA-Ch08-pp38_物理_自然科学_专业资料。文档均来自网络,如
数字电子技术基础 ch08-1_图文.ppt
数字电子技术基础 ch08-1 - 8.1 只读存储器(ROM) 8.1.1 固
Ch08-2应用概率统计 陈魁汇编_图文.pdf
Ch08-2应用概率统计 陈魁汇编 - 第2 节 参数的区间估计 一、区间估计的
crypto4c-ch08-数论入门_图文.ppt
crypto4c-ch08-数论入门 - B 密码编码学与网络安全 电子工业出版
ch08 - 字符串和文本IO_图文.ppt
ch08 - 字符串和文本IO - Java程序设计 第8章 字符串和文本I/O
Ch08_AutocCAD实用工具及图纸输出-TM_图文.ppt
Ch08_AutocCAD实用工具及图纸输出-TM - 主讲:吴起星 力学与土木
operating system操作系统-ch08-main memory-57_图文.ppt
operating system操作系统-ch08-main memory-57
operating system《操作系统》ch08-main memory-57_图文.ppt
operating system《操作系统》ch08-main memory-5
ch08_创建和管理表_图文.ppt
ch08_创建和管理表 - 第8章 创建和管理表 本章目标 通过本章学习,您将可
ch08-2康华光 数字电子技术 第六版_图文.ppt
ch08-2康华光 数字电子技术 第六版 - 8.2 现场可编程门阵列(FPGA
第四章 堆和不相交集数据结构..doc
1 21 2 25 4 25* 5 16 6 08 49 4 25* i 3 2 25 i 1 21 3 49...ch04 堆和不相交集数据结... 30页 免费 第四章不相交集数据结构... ...
大学物理第15讲ch08-4(2011-4-19)_图文.ppt
大学物理第15讲ch08-4(2011-4-19) - 同学们好! A.爱因斯坦
ch08_图文.ppt
ch08_工学_高等教育_教育专区。第八章 大比例尺地形图测绘 本章主要内容如下...(3)除在悬崖或绝壁处外,等高线在图上不能相交或重合。 (4)等高线的平距小,...
Ch08入侵检测技术_图文.ppt
Ch08入侵检测技术 - 网络与信息安全 Ch08 入侵检测技术 本章学习目的
ch08 - 字符串和文本IO_图文.pdf
ch08 - 字符串和文本IO_学习总结_总结/汇报_实用文档。Java程序设计
第四章 堆和不相交集数据结构.pdf
第四章 堆和不相交集数据结构 - 第4章 堆和不相交集数据结构 1、 堆的定义