《数据结构：思想与方法-翁惠玉-27783第十一章》由会员分享，可在线阅读，更多相关《数据结构：思想与方法-翁惠玉-27783第十一章（47页珍藏版）》请在金锄头文库上搜索。
1、1,第11章 不相交集合类,等价关系与等价类 不相交集 不相交集的实现 不相交集类的实现 不相交集的应用,主要用来解决等价问题,2,等价关系,对集合中的每一对元素(a,b), a,bS, aRb要么是真要么是假，则称关系R（relation R）是定义在集合S上。如果aRb为真，则称a与b相关。如果集合中的每一对元素不是有关系就是没关系，则称该关系（relation）是定义在该集合上的。 等价关系（equivalence relation）是一种满足以下三个特性关系R。 自反性（Reflexive）：对所有的aR，aRa为真。 对称性（Symmetric）：当且仅当bRa时，aRb。 传递性（
2、Transitive）：aRb和bRc隐含aRc。,3,等价关系实例,亲戚关系就是一个等价关系。自己和自己是亲戚；如果A和B是亲戚，则B和A也是亲戚；如果A和B是亲戚，B和C是亲戚，则A和C也是亲戚。因此，亲戚关系具有自反性、对称性和传递性，所以是等价关系。 同样，如果通过公路可以从小镇a到小镇b，则称a与b是有关系的。如果道路是双向的，那么公路交通网络中的到达关系也是一个等价关系。,4,等价关系的基本操作,判断两个元素之间是否有等价关系 在两个元素间添加等价关系,5,动态等价问题,等价关系可被表示为布尔型的二维数组，则可以在常量时间内测试等价性。问题在于关系通常是隐式，而不是显式定义的 例如
3、，一个等价关系定义在一个五个元素a1,a2,a3,a4,a5的集合上。该集合产生25对元素，每一对不是有关系就是没有关系。然而，a1a2,a3a4,a1a5和a4a2的信息隐含了所有的元素对都是有关系的。,6,等价类,等价关系的另一种表示方法是采用等价类 集合S中的元素x的等价类是S的一个子集，它包含了所有与x有关的元素。这些等价类形成了不相交的集合 等价类形成了S的一种分割,7,第11章 不相交集合类,等价关系与等价类 不相交集 不相交集的实现 不相交集类的实现 不相交集的应用,主要用来解决等价问题,8,不相交集合,等价类形成了集合S的一种分割。对于任意两个等价类Si和Sj，SiSj=，将所
4、有的等价类并起来就是集合S。 任何两个子集没有共同的元素的集合称为不相交集合。,9,不相交集合类的基本操作,find操作：找出特定元素属于哪个等价类） union操作：用于添加关系。如果要把序偶(a, b)加到关系表中，则与a相关的元素都与b相关，与b相关的元素也都与a相关。即a的等价类与b的等价类合并为一个等价类。 不相交集也称为并查集,10,第11章 不相交集合类,等价关系与等价类 不相交集 不相交集的实现 不相交集类的实现 不相交集的应用,主要用来解决等价问题,11,不相交集的实现,不相交集的存储实现 不相交集的运算实现 改进的union算法 改进的find算法,12,不相交集合类的特点
5、,并不关心元素具体的值，只关心他们的一个标识。因此可简单将这些元素顺序编号为0 N-1 在查找操作时，我们并不关心等价类的名字，只需要知道当a和b在一个等价类中时，find的结果是相同的,13,解决策略,方法一：用线性表保存集合。线性表的第i个元素保存每个第i个元素所属的等价类名。find是O(1)的。union是线性时间。 方法二：用树保存集合，保证union是常量时间，而查找可以达到O（logN）,14,基本的数据结构,每个等价类表示为一棵树，等价类的名字为根结点的名字。这棵树不一定是二叉树。整个集合是一片森林 因为每个节点只需要知道父节点，可以采用双亲表示法，用一个数组保存。数组si的值
6、为i的父节点的下标。如si=-1，表示i是某棵树的根。,15,16,不相交集的实现,不相交集的存储实现 不相交集的运算实现 改进的union算法 改进的find算法,17,基本操作的实现,为了执行两个集合的union操作，我们归并这两棵树，将一棵树的根作为另一棵树的孩子。这个操作很明显是常量时间。 元素x的find操作返回包含x的树的根。完成该操作的时间正比于从x到根的路径上的结点数。最坏情况可能是O(N)。,18,例如：查找12所属的子集 将4和6归并起来,19,不相交集的实现,不相交集的存储实现 不相交集的运算实现 改进的union算法 改进的find算法,20,改进的union算法,尽管
7、不相交集的union操作性能很好，而find操作的性能不佳。但find操作的性能问题是由union操作引起的。是union操作实现时没有关心所构造的树的结构。 在极端的情况下，union操作可能使树蜕化为线性表。 改进的思想：尽量避免树的增高 按规模并 按高度并,21,按规模归并,将规模小的树作为规模大的树的子树，对规模相同的树可以任意选择 例如归并4和9，如将9作为4的子树，形成一棵高度为5的树。但将4作为9的子树，形成的树高度还为4,22,按规模并的最坏情况,每次都是归并两个等规模的集合。每归并一次，高度增加一层。,23,按规模并的实现,需要记录每棵树的规模 解决方法：使根的数组项包含一个
8、负的树规模 。执行union操作时，先检查规模，再决定谁并到谁,24,执行union（4，9）,25,按高度归并,记录了树的高度而不是树的规模，通过将较浅的树作为较深的树的子树完成归并操作。 保证了对数的find操作,26,执行union（4，9）,27,不相交集的实现,不相交集的存储实现 不相交集的运算实现 改进的union算法 改进的find算法,28,改进的find算法,不相交集中，每棵子树的最理想的状态是一棵二层的数，只有根结点和它的儿子。这时，find操作的效率最高。 改进的union算法可以降低树的高度，提高find的效率。但当被归并的两棵树规模相同或高度相同时，树高还是会增加。
9、另外一种效率的改进方法是通过find操作，这种方法称为路径压缩。,29,路径压缩,当对find（x）采用路径压缩方法的话，那么在从x到根结点的路径上的每一个结点都将自己的父结点改为根结点。 如果x是一个很深的结点，这一改进将会大大降低树的高度 路径压缩能与按规模归并完美地兼容。路径压缩与按高度归并不完全兼容，,30,find（14）前,find（14）后,31,第11章 不相交集合类,等价关系与等价类 不相交集 不相交集的实现 不相交集类的实现 不相交集的应用,主要用来解决等价问题,32,不相交集类的实现,采用按规模并和路径压缩,class DisjointSet private: int s
10、ize; int *parent; public: DisjointSet(int s) ; DisjointSet() delete parent; void Union(int root1, int root2); int Find(int x); ;,33,构造函数的定义,DisjointSet:DisjointSet(int n) size = n; parent = new int size; for (int i=0; isize; +i) parenti = -1; ,34,Find函数的实现,int DisjointSet:Find(int x) if (parentx 0)
11、return x; return parentx = Find(parentx); ,如何在查找的过程中改变结点的父结点,35,Union函数的实现,void DisjointSet:Union(int root1, int root2) if (root1 = root2) return; if (parentroot1 parentroot2) parentroot2 += parentroot1; parentroot1 = root2; else parentroot1 += parentroot2; parentroot2 = root1; ,36,第11章 不相交集合类,等价关系与
12、等价类 不相交集 不相交集的实现 不相交集类的实现 不相交集的应用,主要用来解决等价问题,37,不相交集的应用,迷宫问题 最近共同祖先问题,38,应用迷宫问题,把迷宫看成由MN个矩形单元组成，入口在左上角，出口在右下角。左上角的单元与右下角的单元是连通的，单元之间用墙隔开。,一个55的迷宫,39,生成迷宫的算法,开始时假设所有的地方都有墙（除了入口和出口），所有的单元都不连通。 我们不断地随机选择一堵墙，如果由该墙分割的单元互相之间没有连通，则把墙拆除。 重复上述过程，直到连通了入口和出口，就得到了一个迷宫。 继续拆墙直到从每一个单元都能到达其他任一单元当然更好，因为这样做会在迷宫中生成更多的
13、错误路径,40,实现,如果把连通看成一个关系，则该关系是一个等价关系。 迷宫问题转化成等价类的归并问题。 开始时，每个单元是一个等价类。 选择相邻两个单元，判别是否在一个等价类。如果不是，敲开两个单元之间的墙，使之连通。归并两个等价类。 重复上述过程，直到所有单元都在一个等价类中。,41,初始的配置,某些墙已经被拆除。此时，如果我们随机选择8和13之间的墙，这堵墙不用拆掉，因为8和13已经连通,我们随机选择了18和13之间的墙；因为18和13没有连通，这堵墙被拆除,42,迷宫生成,void createPuzzle(int size) /size为迷宫的规模 int num1, num2; D
14、isjointSet ds(size*size); srand(time(0); while (ds.Find(0) != ds.Find(size*size-1) while (true) /选择两个相邻的不连通单元 num1 = rand() * size * size / (RAND_MAX + 1); num2 = num1-size; /检查上方的单元 if (num2 = 0) if (ds.Find(num1) != ds.Find(num2) break; num2 = num1 - 1; /检查左边的单元 if (num1 % size != 0) if (ds.Find(n
15、um1) != ds.Find(num2) break; num2 = num1 + size; /检查下方的单元 if (num2 , “; ,43,不相交集的应用,迷宫问题 最近共同祖先问题,44,最近共同祖先问题,给定一棵树和一个树中的结点对，找出这对结点的最近的共同祖先 结点13和14的最近的共同祖先是12。12和8的最近共同祖先是3。而7和1的最近共同祖先是0,45,解决方案,用后序遍历加上不相交集共同完成。 我们将每一棵子树看成是一个等价类，子树的根是等价类的标志。 按后序遍历这棵树，在后序遍历的过程中计算每个结点的等价类，每次生成一个新的等价类后，就检查结点对中的两个结点是否在一个等价类中。如果在，这个等价类的标志就是他们的共同祖先。,46,找5和11的最近共同祖先,后序遍历1，5和11不在一个等价类 后序遍历2，5和11不在一个等价类 后序遍历3，5和11不在一个等价类 访问根结点0，5和15在一个等价类，等价类的标志是0，他们的共同祖先为0,47,作业,P335 1, 4,
