简单不相交集的合并算法

1、简单不相交集的合并算法 本节的假定前提：1、为算法书写方便起见，设任一集合 都是1,2,n的子集；2、任意两个被合并的集合都是不相交的；3、集合上的运算 只有Union和Find。Union(I,J,K):把名为I与J的集合进行合并，合并后的集合名为K。初始共有n个单元素集，故Union最多可执行n-1次即O(n)。Find(a):给出a所在的集合名(算法中大多用数字表示集合名)。此类问题中Find指令的执行通常也有 O(n)次，故一般 讨论执行O(n)条Union和Find指令所需要的时间。可以用来表示集合的数据结构很多，用什么样的算法和结构才能使得完成上述任务的时间最少？Union(I,J

2、,K)算法中的数组说明：为加快处理速度，每个集合给予一个内部名和一个外部名。内部名与外部名1 1对应。例如：外部名123集合1,3,5,72,4,86内部名231算法涉及6个数组，4个与集合相关，2个与元素相关。数组元素 External-NameS:内部名为S（数字）的集合所对应的外部名。数组元素 Internal-NameL:外部名为L（数字）的集合所对应的内部名。数组元素Ri:给出元素i所属集合的内部名。（Find指令可在O（1）时间内完成）Nexti:给出与元素i同在一个集合中的下一个元素，内容为0时，表示无下一元素（即元素i是该集合的最后一个元素）。数组元素ListS:给出内部名为S

3、的集合中的第一个元素。数组元素SizeS:给出内部名为S的集合中的元素个数。AInternal-NameI;/*将集合外部名I,J转为内部名A和B*/B -Internal-NameJ;wlg assume SizeA - SizeB/*A为小集合，B为大集合*/otherwise interchange roles of A and B inELEMENT - ListA;/*找出集合A的第一个元素*/while ELEMENT * 0 do/*不断把 A 中*/*元素所在的集合名改为B,直到全部改完为止*/RELEMENT B;/* 改名*/LAST ELEMENT;/*记下当前元素 */

4、ELEMENT - NextELEMENT;/*更新当前元素，准备执行下一轮*/*循环结束时，*/*LAST中记录了原集合A中的最后一个元素*/NextLAST - ListB;/*置该元素的下一个元素为原B中的第一个元素，*/*从而实现A和B的合并*/ListB - ListA;/*置合并后的首元素为原 A中的首元素*/SizeB -SizeA + SizeB;/*置集合大小为A、B两集合的规模之和*/Internal-NameK B;/*建立新集合的内部名与外部名的对应关系*/External-NameB K Union算法除6-9行以外，其余均为常数时间。在最坏情况下，即当 A和B的规模

5、均为n/2时，6-9行要执行n/2次，以完成其中一个集合的元素所属集改 名。即最坏情况下执行1次Union需要的时间为0 (n)。在最坏情况下，执行n-1次Union需要的时间是否为0 (n2)?对6-9行进行总体分析,即考虑执行n-1次Union需要的总时间 TOC o 1-5 h z 每次总是小集合中的元素所属集合改名，每执行一次Union ,被改名元素所在集合的规模至少扩大一倍。考虑任意一个元素i能够被改名的次数：初始时i所在集合只有一个元素，改名一次以后，i所在集合的元素至少有2个，再改名一次以后，i所在集合的元素至少有 4个， 故当i改名k次后，i所在集合的元素至少有 2k个，而2k

6、 * n是必须满足的，故有 k * Log 2n ,即任一元素i最多被改名Log 2n次(i=1,2，,n), 故n个元素的改名总次数不会超过n*Log 2n ,即在n-1次Union中，6-9行执行改名的次数不超过 0 (n logn)。在最坏情况下，改名总次数是可能达到。(n logn)的：E.g.设n=2k,先把单元素集两两合并为双元素集；再把双元素集两两合并为 4元素集；最后把两个n/2元素集合并为一个总的 n元素集。在上述每一轮，需要改名的元素恰好为n/2个，共执行k=Log 2n轮，故改名的总次数为 1/2*nLog 2n。 说明：若没有内部名，则每次合并时两个集合中的所有元素均要改名(改为K),这样，在n-1次Union中改名的次数就会大大超过上述方式O另外，如果合并时不进行外部命名，即用Union（I,J）的形式，则不需要另外再建立内部名，合并时仍然是小集合中的元素改名。总的开销比上述算法少一些，（减