簡單不相交集的合并算法

1、簡單不相交集的合并算法 本節(jié)的假定前提：1、為算法書寫方便起見，設(shè)任一集合 都是1,2,n的子集；2、任意兩個被合并的集合都是不相交的；3、集合上的運算 只有Union和Find。Union(I,J,K):把名為I與J的集合進行合并，合并后的集合名為K。初始共有n個單元素集，故Union最多可執(zhí)行n-1次即O(n)。Find(a):給出a所在的集合名(算法中大多用數(shù)字表示集合名)。此類問題中Find指令的執(zhí)行通常也有 O(n)次，故一般 討論執(zhí)行O(n)條Union和Find指令所需要的時間。可以用來表示集合的數(shù)據(jù)結(jié)構(gòu)很多，用什么樣的算法和結(jié)構(gòu)才能使得完成上述任務(wù)的時間最少？Union(I,J

2、,K)算法中的數(shù)組說明：為加快處理速度，每個集合給予一個內(nèi)部名和一個外部名。內(nèi)部名與外部名1 1對應(yīng)。例如：外部名123集合1,3,5,72,4,86內(nèi)部名231算法涉及6個數(shù)組，4個與集合相關(guān)，2個與元素相關(guān)。數(shù)組元素 External-NameS:內(nèi)部名為S（數(shù)字）的集合所對應(yīng)的外部名。數(shù)組元素 Internal-NameL:外部名為L（數(shù)字）的集合所對應(yīng)的內(nèi)部名。數(shù)組元素Ri:給出元素i所屬集合的內(nèi)部名。（Find指令可在O（1）時間內(nèi)完成）Nexti:給出與元素i同在一個集合中的下一個元素，內(nèi)容為0時，表示無下一元素（即元素i是該集合的最后一個元素）。數(shù)組元素ListS:給出內(nèi)部名為S

3、的集合中的第一個元素。數(shù)組元素SizeS:給出內(nèi)部名為S的集合中的元素個數(shù)。AInternal-NameI;/*將集合外部名I,J轉(zhuǎn)為內(nèi)部名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;/*更新當前元素，準備執(zhí)行下一輪*/*循環(huán)結(jié)束時，*/*LAST中記錄了原集合A中的最后一個元素*/NextLAST - ListB;/*置該元素的下一個元素為原B中的第一個元素，*/*從而實現(xiàn)A和B的合并*/ListB - ListA;/*置合并后的首元素為原 A中的首元素*/SizeB -SizeA + SizeB;/*置集合大小為A、B兩集合的規(guī)模之和*/Internal-NameK B;/*建立新集合的內(nèi)部名與外部名的對應(yīng)關(guān)系*/External-NameB K Union算法除6-9行以外，其余均為常數(shù)時間。在最壞情況下，即當 A和B的規(guī)模

5、均為n/2時，6-9行要執(zhí)行n/2次，以完成其中一個集合的元素所屬集改 名。即最壞情況下執(zhí)行1次Union需要的時間為0 (n)。在最壞情況下，執(zhí)行n-1次Union需要的時間是否為0 (n2)?對6-9行進行總體分析,即考慮執(zhí)行n-1次Union需要的總時間 TOC o 1-5 h z 每次總是小集合中的元素所屬集合改名，每執(zhí)行一次Union ,被改名元素所在集合的規(guī)模至少擴大一倍。考慮任意一個元素i能夠被改名的次數(shù)：初始時i所在集合只有一個元素，改名一次以后，i所在集合的元素至少有2個，再改名一次以后，i所在集合的元素至少有 4個， 故當i改名k次后，i所在集合的元素至少有 2k個，而2k

6、 * n是必須滿足的，故有 k * Log 2n ,即任一元素i最多被改名Log 2n次(i=1,2，,n), 故n個元素的改名總次數(shù)不會超過n*Log 2n ,即在n-1次Union中，6-9行執(zhí)行改名的次數(shù)不超過 0 (n logn)。在最壞情況下，改名總次數(shù)是可能達到。(n logn)的：E.g.設(shè)n=2k,先把單元素集兩兩合并為雙元素集；再把雙元素集兩兩合并為 4元素集；最后把兩個n/2元素集合并為一個總的 n元素集。在上述每一輪，需要改名的元素恰好為n/2個，共執(zhí)行k=Log 2n輪，故改名的總次數(shù)為 1/2*nLog 2n。 說明：若沒有內(nèi)部名，則每次合并時兩個集合中的所有元素均要改名(改為K),這樣，在n-1次Union中改名的次數(shù)就會大大超過上述方式O另外，如果合并時不進行外部命名，即用Union（I,J）的形式，則不需要另外再建立內(nèi)部名，合并時仍然是小集合中的元素改名?？偟拈_銷比上述算法少一些，（減