并查集及其应用演示版.ppt

并查集及其应用 三、并查集的实现及优化 2、并查集的链表实现 我们需要用一定的数据结构来组织动态的集合，同一集合中的所有元素应该是联系在一起的。一种比较简单的想法是用链表来实现，每个集合对应一个链表，它有一个表头，每一个元素有一个指针指向表头，表明了它所属的类，另有一个指针指向它的下一个元素,同时为了方便实现，再设一个指针last表示链表中的最后一个元素（表尾）。可以选择静态数组（一般来说这种问题处理的对象都是连续整数，可以用下标来对应元素）来实现，定义一个记录为： type node = record head,next,last:integer; end; var S : array[1..maxn] of node; .......... * 并查集及其应用 三、并查集的实现及优化 2、并查集的链表实现 可以得到MAKE-SET和FIND-SET的实现为： MAKE-SET(x) { S[x].head = x;S[x].next = 0; } FIND-SET（x） { return S[x].head } 两个过程的时间复杂度都为O(1)。注意到我们采用链表以后，当有两个元素(x,y),FIND-SET（x）≠FIND-SET（y）时，两者对应不同的集合，需要将两个链表合并，做法是将一个表的表头直接接到另一个表的表尾，这步操作很简单，但势必造成修改后需要把接上去的那个表的所有head值修改，这需要线性的赋值操作，其复杂度与选择接在尾部的链表长度成正比。 .......... * 并查集及其应用 三、并查集的实现及优化 2、并查集的链表实现 现在讨论UNION(x,y)的实现，假设UNION(x,y)的参数是有序的，即把y属于的集合合并到x的集合。有两种实现方法： （1）简单实现 不考虑任何因素，出现FIND-SET（x）≠FIND-SET（y）时，直接将y的表头接到x的尾，同时将y中所在集合元素所有元素的head设为FIND-SET(x)。同时x的表尾也应该设为原y的表尾。注意last指针其实只要在表头结点中记录即可，因为每一次查到FIND-SET（x）都可以得到表头元素。而链表中其他元素重新记录last是无意义的。 考虑输入数据的特殊性，我们总是把y接到x里去，那么如果y所在的集合非常大，每次赋值的代价就会非常高，比如出现输入为： （2，1），（3，1），（4，1），（5，1），（6，1） ， … ，(n,1) 显然y所在的集合越来越庞大，对于这种方法最坏情况下时间复杂度为O(n^2)。 .......... * 并查集及其应用 三、并查集的实现及优化 2、并查集的链表实现 （2）快速实现 上述简单实现非常不理想，针对y可能比较大的这个问题，可以很快产生一个聪明的想法：不妨比较x和y所在集合的大小，从而作出选择，把较短的链表接在较长的尾部，这样效果是一样的，但耗费肯定不比原来差。这就是快速实现的思路。可以在node里多设一个域number，用来记录此条链表中成员的个数。显然number记录在表头元素中即可，将两表合并的时候，只要将表的number相加，因此维护起来是非常方便的。 这种快速实现的方法可以称为加权启发式合并，这里的权就是指所记录的number。 .......... * 并查集及其应用 三、并查集的实现及优化 2、并查集的链表实现 可以证明这种方法的效率。当有n个元素时，在UNION上的花费（即重新赋值的次数）的上界是O(nlog2n)。考虑一个固定的对象x，当x的代表指针（head）被更新时，x必是属于一个较小的集合，因此，x的代表指针第一次更新后，结果集合必然至少有2个元素，类似的，下一次更新后，x所在的集合至少有4个元素。继续下去，可以发现，x的代表指针最多被更新log2n次，因为当x所在集合元素已经等于n以后，不可能再发生UNION操作。所以，总共有n个元素时，操作的总次数不超过nlog2n次。这就保证了整个算法的复杂度是理想的。 .......... * 并查集及其应用 三、并查集的实现及优化 2、并查集的链表实现 合并两个集合时的实现过程如下： UNION(x,y) { x = FIND-SET(x); y = FIND-SET(y); if x.numbery.number then UNION(x,y) else UNION(y,x); } 并查集的链表实现是一种非常容易接受的算法，并且它的效率也是令人满意的。其实它的思路和数组完全一样，所以实际使用较少。