并查集

维基百科,自由的百科全书
跳转至: 导航搜索
MakeSet建立了8个元素。
在几次Union操作后,一些集合合并在一起。

计算机科学中,并查集是一种树型的数据结构,其保持着用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。有一个联合-查找算法union-find algorithm)定义了两个操作用于此数据结构:

  • Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union:将两个子集合并成同一个集合。

因为它支持这两种操作,一个不相交集也常被称为联合-查找数据结构(union-find data structure)或合并-查找集合(merge-find set)。其他的重要方法,MakeSet,用于建立单元素集合。有了这些方法,许多经典的划分问题可以被解决。

为了更加精确的定义这些方法,需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素,称为代表,以表示整个集合。接着。Find(x)返回x所属集合的代表,而Union使用两个集合的代表作为参数。

并查集森林[编辑]

并查集森林是一种将每一个集合以表示的数据结构,其中每一个节点保存着到它的父节点的引用(见意大利面条堆栈)。这个数据结构最早由Bernard A. GallerMichael J. Fischer于1964年提出,[1]但是经过了数年才完成了精确的分析。

在并查集森林中,每个集合的代表即是集合的根节点。“查找”根据其父节点的引用向根行进直到到底树根。“联合”将两棵树合并到一起,这通过将一棵树的根连接到另一棵树的根。实现这样操作的一种方法是:

 function MakeSet(x)
     x.parent := x
 function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

这是并查集森林的最基础的表示方法,这个方法不会比链表法好,这是因为创建的树可能会严重不平衡;然而,可以用两种办法优化。

第一种方法,称为“按秩合并”,即总是将更小的树连接至更大的树上。因为影响运行时间的是树的深度,更小的树添加到更深的树的根上将不会增加秩除非它们的秩相同。在这个算法中,术语“秩”替代了“深度”,因为同时应用了路径压缩时(见下文)秩将不会与高度相同。单元素的树的秩定义为0,当两棵秩同为r的树联合时,它们的秩r+1。只使用这个方法将时最坏的运行时间提高至每个MakeSet、Union或Find操作O(\log n)。优化后的MakeSetUnion伪代码:

 function MakeSet(x)
     x.parent := x
     x.rank   := 0
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot == yRoot
         return

     // x和y不在同一个集合,合并它们。
     if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1

第二个优化,称为“路径压缩”,是一种在执行“查找”时扁平化树结构的方法。关键在于在路径上的每个节点都可以直接连接到根上;他们都有同样的表示方法。为了达到这样的效果,Find递归地经过树,改变每一个节点的引用到根节点。得到的树将更加扁平,为以后直接或者间接引用节点的操作加速。这儿是Find

 function Find(x)
     if x.parent != x
        x.parent := Find(x.parent)
     return x.parent

这两种技术可以互补,可以应用到另一个上,每个操作的平均时间仅为O(\alpha(n))\alpha(n)n = f(x) = A(x,x)反函数,并且A是急速增加的阿克曼函数。因为\alpha(n)是其的反函数,\alpha(n)对于可观的巨大n还是小于5。因此,平均运行时间是一个极小的常数。

实际上,这是渐近最优算法Fredman和Saks在1989年解释了\Omega(\alpha(n))的平均时间内可以获得任何并查集。[2]

主要操作[编辑]

需要注意的是,一开始我们假设元素都是分别属于一个独立的集合里的。

合并两个不相交集合[编辑]

操作很简单:先设置一个数组Father[x],表示x的“父亲”的编号。 那么,合并两个不相交集合的方法就是,找到其中一个集合最父亲的父亲(也就是最久远的祖先),将另外一个集合的最久远的祖先的父亲指向它。

Pascal代码:

procedure Union(x,y:integer);{其中GetFather是下面将讲到的操作}
 var fx,fy : integer;
  begin
     fx := getfather(x);
     fy := getfather(y);
     If fx<>fy then father[fx] := fy;{指向最祖先的祖先}
  end;

C语言代码表示形式:

void Union(int x,int y)
{
    fx = getfather(x);
    fy = getfather(y);
    if(fy!=fx)
       father[fx]=fy;
}

判断两个元素是否属于同一集合[编辑]

仍然使用上面的数组。则本操作即可转换为寻找两个元素的最久远祖先是否相同。寻找祖先可以采用递归实现,见后面的路径压缩算法。


Pascal代码:

Function Same(x,y:integer):boolean;
begin
  if GetFather(x)=GetFather(y) then 
    exit(true) else
    exit(false);
end;

C代码:

bool same(int x,int y)
{
   return getfather(x)==getfather(y);
}
/*返回true 表示相同根结点,返回false不相同*/

并查集的优化[编辑]

路径压缩[编辑]

刚才我们说过,寻找祖先时采用递归,但是一旦元素一多起来,或退化成一条链,每次GetFather都将会使用O(n)的复杂度,这显然不是我们想要的。

对此,我们必须要进行路径压缩,即我们找到最久远的祖先时“顺便”把它的子孙直接连接到它上面。这就是路径压缩了。使用路径压缩的代码如下:

Function getfather(v:integer):integer;
  begin
    if (father[v]=v) then
      getfather:=v
    else
      begin
        father[v]:=getfather(father[v]);{路径压缩}
        getfather:=father[v];
      end;
  end;
int getfather(int v)
{
    if (father[v]==v)
      return v;
    else
    {
        father[v]=getfather(father[v]);//路径压缩
        return father[v];
     }
}
Procedure Initialize;
var
  i:integer;
begin
  for i:=1 to maxv do 
    Father[i]:=i;
end;
 
Function GetFather(v:integer):integer;
begin
  if Father[v]=v then 
    exit(v) else
    Father[v]:=getfather(father[v]);{路径压缩}
  exit(Father[v]);
end;

Rank合并[编辑]

合并时将元素所在深度低的集合合并到元素所在深度高的集合。

function judge(x,y:integer):boolean;
 var fx,fy : integer;
  begin
     fx := getfather(x);
     fy := getfather(y);
     If fx=fy then 
       exit(true) else 
       judge := false;
     if rank[fx]>rank[fy] then
       father[fy] := fx else begin
       father[fx] := fy;
       if rank[fx]=rank[fy] then 
         inc(rank[fy]);
     end;
  end;

初始化:

fillchar(rank,sizeof(rank),0);

C语言代码: 合并时将元素所在深度低的集合合并到元素所在深度深的集合。

void judge(int x ,int y)
 
{
     fx = getfather(x);
     fy = getfather(y);
 
     if (rank[fx]>rank[fy])
        father[fy] = fx;
     else
     {
        father[fx] = fy;
        if(rank[fx]==rank[fy])
           ++rank[fy]; //重要的是祖先的rank,所以只用修改祖先的rank就可以了,子节点的rank不用管
     }
}

初始化:

memset(rank,0,sizeof(rank));

源代码[编辑]

加了所有优化的代码框架:

function getfather(v:longint):longint;
begin
  if father[v]=v then
    exit(v) else
     father[v]:=getfather(father[v]);
    exit(father[v]);
end;

时间及空间复杂度[编辑]

它使用O(n)的空间(n为元素数量),单次操作的均摊时间为O(\alpha(n))。其中\alpha(n)f(n)=A(n,n)的反函数,而A(n,n)阿克曼函数

应用[编辑]

Kruskal算法的优化

註釋[编辑]

  1. ^ Galler, Bernard A.; Fischer, Michael J., An improved equivalence algorithm, Communications of the ACM. May 1964, 7 (5): 301–303 . The paper originating disjoint-set forests.
  2. ^ Fredman, M.; Saks, M., The cell probe complexity of dynamic data structures, Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing. May 1989: 345–354, "Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets."