什么是并查集
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; // 用来获取组件标识（component identifier）
int Count; // 组件数量
MakeSet(int n){
Count = n;
id(n);
for(int i = 0; i < n; i++)
id[i] = i;
}
-
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拥有其唯一的根节点 ( root )，其父节点是它自己或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;
}
- 在合并时，将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 《零起步学算法》.