1、 简述
并查集(Disjoint set或是Union-find set)是一种树形的算法设计,常见于解决一些不交叉结合(Disjoint Sets)的合拼及查看难题。
2、 操作过程
并查集是一种比较简单的算法设计,它关键涉及到2个操作过程,各自为:
A. 合拼2个不交叉结合
B. 分辨2个原素是不是归属于同一个结合
(1) 合拼2个不交叉结合(Union(x,y))
合拼实际操作非常简单:先设定一个二维数组Father[x],表明x的“爸爸”的序号。那麼,合拼2个不交叉结合的方式便是,寻找在其中一个结合最爸爸的爸爸(也就是最悠久的先祖),将此外一个结合的最悠久的先祖的爸爸偏向它。
图中为2个不交叉结合,b图为合拼后Father(b):=Father(g)
(2) 分辨2个原素是不是归属于同一结合(Find_Set(x))
本实际操作可变换为找寻2个原素的最悠久先祖是不是同样。能够选用递归完成。
3、 提升
(1) Find_Set(x)时,途径缩小
找寻先祖时,大家一般选用递归搜索,可是当原素许多 亦或是整棵树变成一条链时,每一次Find_Set(x)全是O(n)的复杂性。为了更好地防止这类状况,大家需对途径开展缩小,即在我们历经”递推”寻找先祖连接点后,”回朔”的情况下顺带将它的子孙后代连接点都立即偏向先祖,那样之后再度Find_Set(x)时复杂性就变为O(1)了,如下图所显示。由此可见,途径缩小便捷了之后的搜索。
(2) Union(x,y)时,按秩合拼
即合拼的情况下将原素少的结合合拼到原素多的结合中,那样合拼以后树的高宽比会相对性较小。
4、 程序编写完成
int father[MAX]; /* father[x]表明x的父节点 */ int rank[MAX]; /* rank[x]表明x的秩 */ /* 复位结合 */ void Make_Set(int x) { father[x] = x; //父节点给自己(依据具体情况特定父节点可转变) rank[x] = 0; //秩为0(依据具体情况复位秩还可以有一定的转变) } /* 搜索x原素所属的结合,回朔时缩小途径 */ int Find_Set(int x) { if (x != father[x]) { rank[father[x]] = rank[x]; //递归,以寻找最悠久先祖 //回朔时缩小途径:途径上的全部子孙后代连接点都偏向最悠久先祖 father[x] = Find_Set(father[x]); } return father[x]; } /* 按秩合拼x和y所属的结合 下边的那一个if else构造并不是肯定的,实际依据状况转变 可是,服务宗旨是不会改变的即,按秩合拼,自动更新秩。 */ void Union(int x, int y) { x = Find_Set(x); //寻找最悠久先祖 y = Find_Set(y); if (x == y) return; //2个原素归属于同一个结合 if (rank[x] > rank[y]) //把深层小的结合合拼到深层大的结合中去 { father[y] = x; rank[x] = rank[y]; //升级合拼后的深层 } else { if (rank[x] == rank[y]) { rank[y] ; } father[x] = y; } }
5、 复杂性剖析
空间复杂度为O(N),创建一个结合的算法复杂度为O(1),N次合拼M搜索的算法复杂度为O(M Alpha(N)),这儿Alpha是Ackerman涵数的某一反函数,在非常大的范畴内(人们现阶段观察到的宇宙空间范畴估计有10的80三次方个分子,这低于前边常说的范畴)这一涵数的值能够当做是不超4的,因此并查集的实际操作能够当作是线形的。实际复杂性剖析全过程见参考文献(3)。
6、 运用
并查集常做为另一种繁杂的算法设计或是优化算法的存储结构。普遍的运用有:求无向图的连通分量数量,近期公共性先祖(LCA),带限定的工作排列,完成Kruskar优化算法求最小生成树等。
7、 参考文献
(1) 并查集:http://www.nocow.cn/index.php/并查集
(2) 博闻《并查集详解》:http://www.cnblogs.com/cherish_yimi/
(3) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp. 498–524.