void Union (UFSets *S, int RootI, int Root2)i //求两个不相交集合R00t1与R00t2的并 S-> parent Root+- S-> parent Root2 S-> parent Root2-Rootl; 将R002连接到R00t1下面 Find和 Union操作性能不好。假设最初n个 元素构成n棵树组成的森林,S-> parenti l。做处理Un0n(n-2,n-12…, Union(, 2), Union(0,1)后,将产生退化的树
11 void Union (UFSets *S, int Root1, int Root2) { //求两个不相交集合Root1与Root2的并 S->parent[Root1] += S->parent[Root2]; S->parent[Root2] = Root1; //将Root2连接到Root1下面 } ◼ Find和Union操作性能不好。假设最初n 个 元素构成 n 棵树组成的森林，S->parent[i] = -1。做处理Union(n-2, n-1), …, Union(1, 2), Union(0, 1)后，将产生退化的树
合并"he2n3ns 3 3 0 2 3 2 Union (3, 4)4 3 3 2) Union (2, 3) 3 3 Union(1, 2) Union(0, 1) 12
12 ◼ 合并 -1 -1 -1 -1 -1 0 2 3 4 -3 -5 0 3 2 1 3 3 4 1 3 3 2 2 0 2 3 1 4 Union(0,1) -2 3 -4 1 4 2 1 2 3 4 Union(1,2) Union(2,3) Union(3,4)
执行一次Umon操作所需时间是01),n-1 次 Union操作所需时间是o(n) 若再执行Find(0,Find(1),…,Find(n-1),若 被搜索的元素为i,完成Find(i)操作需要时 间为0(),完成n次搜索需要的总时间将达 到 O(∑i)=O(n2) a改进的方法 ◆按树的结点个数合并 ◆按树的高度合并 ◆压缩元素的路径长度 13
13 ◼ 执行一次Union操作所需时间是O(1)，n-1 次Union操作所需时间是O(n)。 ◼ 若再执行Find(0), Find(1), …, Find(n-1), 若 被搜索的元素为 i，完成 Find(i) 操作需要时 间为O(i)，完成 n 次搜索需要的总时间将达 到 ◼ 改进的方法 ◆ 按树的结点个数合并 ◆ 按树的高度合并 ◆ 压缩元素的路径长度 = = n i i n 1 2 O( ) O( )
按树结点个数合并 >结点个数多的树的根结点作根 3 5 1-1=1(1 51 0 Union(2,0)2 谷(e 3 9 2 3 263 50
14 ◼ 按树结点个数合并 ➢结点个数多的树的根结点作根 -1 -1 -1 -1 -1 0 1 2 3 4 -1 -1 0 -7 2 5 6 -5 -2 2 2 3 3 2 0 1 3 4 5 6 2 3 3 0 2 0 6 5 2 1 3 4 Union(2, 0)
void WeightedUnion (UFSets *S int Rtl, int Rt2)i ∥/按 Union的加权规则改进的算法 int temp=S->parent[Rtl]+ S-> parent[Rt2; if(S->parent[Rt2<S->parent[Rtl( S-> parentI]=Rt2;/Root2中结点多 S-> parentS2]=temp;/R0ot指向Root2 else S-> parentIrte]=Rtl;/Root中结点多 S-> parent[]=temp;/Ro2指向 RootI 15
15 void WeightedUnion (UFSets *S, int Rt1, int Rt2 ) { //按Union的加权规则改进的算法 int temp = S->parent[Rt1] + S->parent[Rt2]; if ( S->parent[Rt2] < S->parent[Rt1] ) { S->parent[Rt1] = Rt2; //Root2中结点多 S->parent[Rt2] = temp; //Root1指向Root2 } else { S->parent[Rt2] = Rt1; //Root1中结点多 S->parent[Rt1] = temp; //Root2指向Root1 } }