并查集 ( Disjoint-Set or Union-Find data structure )

什么是并查集

1.将n个 不重复的元素 ( distinct elements ), 分配到几个 不相交集合 ( disjoint sets )的应用。

• 换句话说，一个不相交的集合(disjoint sets)是一组集合，其中任何项都不能出现在一个以上的集合中。
  ( A disjoint set is a group of sets where no item can be in more than one set. )
  
• 一般将最终得到的不相交集合称为组件（ component ）.

并查集的操作规范

1.符合并查集问题的元素的一些基本特征：

• 连接没有方向，即a连接b，等同于b连接a.（ 由此此类问题只需要考虑两个节点 是否连通即可 ）
• 连接具有传递性，a连接b，b连接c，等同于a连接c. ( 即所有连接元素处于 同一个集合中或拥有 同一个类别 )

2.基本操作：

  MakeSet(int N);  // initilize N nodes with integer names( 0 to N-1 )
  void Union(int a, int b);  // add connection between a and b
  int Find(int a);  // component identifier for p ( 0 to N-1 )
  boolean Connected(int a, int b)  // return true if a and b are in the same component
  int Count();  // number of components

• MakeSet( int n ) 利用数组id[ ]的 整数不重复索引下标来初始化.

利用数组表达并查集

• 因为并查集的每个元素都是不重复的( distinct element ),所以总是可以利用数组下标[ index ]为整数且互不重复的特性来表达其元素标识(element identifier ).

• 而每个数组元素对应的值（value）用来表示其元素所在组件标识（ component identifier ），其初始化值由其对应的下标来赋值. ( id[ index ] = index )

• [ index ] => element identifier, id[ index ] => component identifier.

  vector<int> id;  // &#x7528;&#x6765;&#x83B7;&#x53D6;&#x7EC4;&#x4EF6;&#x6807;&#x8BC6;&#xFF08;component identifier&#xFF09;
  int Count;  // &#x7EC4;&#x4EF6;&#x6570;&#x91CF;

  MakeSet(int n){
    Count = n;
    id(n);
    for(int i = 0; i < n; i++)
        id[i] = i;
  }
</int>

• boolean Connected( int a, int b ) 判定节点a和b是否拥有同一 component index( 即是否处于同一集合中 ).

  boolean Connected(int a, int b){
      return find(a) == find(b);
  }

• int Count() 以独立节点个数n初始化component的个数，每进行一次Union()操作，将component的个数减1.

  int count(){
    return Count;
  }

基于快速查询( Quick-Find )下的Find()与Union()操作实现

1.通过数组id[ ]获取节点的速度将非常快速.

• int Find(int a) 找到节点a所在component的component identifier.

  int Find(int a){
      return id[a]；
  }

• void Union(int a ,int b) 将a所在集合中的所有同类合并到b的集合中.

  void Union(int a ,int b){
      // 找得到a和b的对应component identifier
      int aID = find(a);
      int bID = find(b);
      // 如何索引值相等，说明在同一集合中，直接返回
      if(aID == bID)  return;
      // 否则将b的索引值赋值给a（即将a合并b所在的集合名称下）
      for(int i = 0; i < id.size(); ++i)
          if (id[i] == aID) id[i] == bID;
      Count--;
  }

Quick-Find 的缺点

• 将a所在component中的所有元素合并到b中，涉及到 对数组id[ ]值的修改操作.

• 意味着需要 对id[ ]数组进行遍历，意味着时间复杂度将几何增加 O(n^2).

基于快速合并( Quick-Union )下的Find()与Union()操作实现

1.为了降低组数修改操作带来的时间复杂度增加，将使用并查集森林( Disjoint-Set Forests ）形式来表达.

依然基于数组结构（id[ ]）下的抽象解释

• 该结构（Disjoint-Set Forests）意味着id[ ]将采用树(tree )结构，并使用 parent-link表达式.

• 虽然初始化数据依然采用数组，但可以将每个组数元素其想象成 独立节点.

• 每个数组元素刚 初始化时，其对应component里只有它自己一个元素，所以其向父节点的连接( parent-link ) 指向它自己( self-link )或Null.

• 利用根节点的唯一性，该component的component identifier使用root节点所对应值.

• int Find(int a) 与Quick-Find中的id[ index ]作为compnont identifier不同，这里的id[ index ]可以理解为[ index ]的联通路径(father identifier).

• 如同一根带箭头的线段，虽然在实际应用中常常省略，因为最终都会连向根节点.

  int Find(int a){
      while(a != id[a]) a = id[a];  // 沿父节点攀爬，直到根节点
      return a;
  }

• void Union(int a ,int b) 将a的根节点指向b的根节点 （即合并后的集合根节点为b，其值作为component identifier）.

  void Union(int a ,int b){
      int aRoot = Find(a);
      int bRoot = Find(b);
      if(aRoot == bRoot) return;

      id[aRoot] = bRoot;  // 将a的根节点，本来是指向自己的箭头，指向了b的根节点
      Count --;

2.Find()在Quick-Union中扮演着重要角色.

• 可以看到，虽然Quick-Union不用遍历数组，但是Find()中的向父节点攀爬过程，如果遇到最坏的情况，即链式结构，其时间复杂度也接近于遍历.

• 并且Union()和Connect()中都会使用到Find()，所以其总的时间复杂度由Find()起到决定作用，而Find()的复杂度又由树结构的高度( height )所影响.

衡量树的名词定义

• 大小( size ): 表示一棵树含有节点的总数.

• 深度( depth ): 表示一个节点到其根节点所进过的连接路径总数.

• 高度( height ): 表示一棵树其中节点深度的最大值.

提高1：在Union()阶段按rank或者size优化的Weighted Quick-Union

1.维护另一个数组来追踪树的大小，在合并时，总是将较小的树合并到较大的树中去，以此来平衡整个树的高度( height ).

• 初始化时增加维护树大小的数组sz[ ]，并将其初始化.

  vector<int> sz;  // size of component for roots
  MakeSet(int n){
      sz(n);
      for(int i = 0; i < n ; ++i) sz[i] = 1;
  }
</int>

• 在合并时，将size较小的树合并到较大中去，并将两者size的相加计入到大树中.

  void Union(int a ,int b){
      int aRoot = Find(a);
      int bRoot = Find(b);
      if(aRoot == bRoot) return;

      if(sz[aRoot] < sz[bRoot]){
          id[aRoot] = bRoot;
          sz[bRoot] += sz[aRoot];
      }
      else {
          id[bRoot] = aRoot;
          sz[aRoot] += sz[bRoot];
      }
      Count --;
  }

提高2: 在Find()阶段使用路径压缩(Path Compression)优化的Weighted Quick-Union

1.不完全压缩：让查询过程中经历的”部分结点”指向它的父亲结点的父亲结点。相对于「完全压缩」而言，压缩没有那么彻底。

• 只需要在Weighted Quick-Union的Find（）中增加一行代码即可.

int Find(int a){
      while(a != id[a]){
          id[a] = id[id[a]];
          a = id[a];
      }
      return a;
  }

2.完全压缩: 让查询根结点的过程中，沿途经过的”所有结点”指向都指向根结点.

int Find(int a){
      if(a != id[a]){
          id[a] = Find(id[a]);
      }
      return id[a];
  }

小结

1.各方法时间复杂度分析:

• 在实际大型问题应用中， Weighted Quick-Union with Path Compression(不完全压缩)非常接近线性时间复杂度，因此成为常用的优化方法.

写在最后

• 作为初学者，我以为算法的学习还是应该以思维训练为主，以此来加深对编程思想的理解.如果仅仅只是当做一个manual来套路化、模板化的使用，虽然能快速入门，不过应该是很难走更远的.

• 写这篇文章之前我在leecode上，google上，看了诸多博主写的关于并查集的文章后. 初衷是想走捷径，快速掌握，不过在实际问题应用分析时，却发现有许多不易察觉的细节难以把控.

• 思来想去还是觉得没有从根上去理解整个算法的核心思想，于是又回到《算法第四版》经典书籍的学习中，搭建起骨架，在遇到难以理解的细节分支，再去google上寻找后来人的各种解读，从而加深理解.

• 经典书籍只所以经典，是因为其经历了时间的考验，其整个思维体系的完整性是一般创作者难以企及的.

主要参考资料

• 《算法第四版》第 1 章第 5 节.

• Leecode 《零起步学算法》.

Original: https://www.cnblogs.com/Dy2MoRaw/p/15899723.html
Author: Dy2MoRaw
Title: 并查集 ( Disjoint-Set or Union-Find data structure )