版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434821
《算法》当中第一章节就介绍了该数据结构,但并不知道它到底有何用,也就一直没有研究它。当做过一系列数组+链表+树的题目之后,再看看这并查集似乎又有点意思了,今天就探寻下。
我对并查集的具体应用还不了解,所以就从一些基本的题目引出并查集。
并查含义:合并集合,查找集合。
可以有的操作如下:
所以基本的并查集API如下:
public class UF {
int[] union;
public UF(int N) {
union = new int[N];
for (int i = 0; i < N; i++){
union[i] = i;
}
}
public void union(int p, int q){
}
public int find(int p){
return 0;
}
public boolean connected(int p, int q){
return false;
}
public int count(){
return 0;
}
public static void main(String[] args) {
In in = new In("./data/tinyUF.txt");
int N = in.readInt();
UF uf = new UF(N);
for (int i = 0; i < N; i++){
int p = in.readInt();
int q = in.readInt();
if (uf.connected(p, q)) continue;
uf.union(p,q);
System.out.println(p + " " + q);
}
System.out.println(uf.count() + " components");
}
}
union的数据结构采用数组形式,数组有两个天然的标识:index和value,所以在并查集应用中,由于index均唯一,所以它们可以代表每一个元素,而value则可以表示集合。
既然,我们能够对数组中的每个value进行操作,且初始化时,所有元素都有一个唯一的集合。union[i] = i
,那么我们就用这唯一的i
作为集合标识。比如:当需要连接p和q时,我们进行如下操作:
union[q] = q -> union[q] = p;
此时集合p中的元素有<p,q>
所以,后续一旦有新的元素要加入到集合p中,如union(x,y)
int id = find(x);
union[y] = id;
代码如下:
public class UF {
int[] union;
int SIZE;
public UF(int N) {
union = new int[N];
for (int i = 0; i < N; i++){
union[i] = i;
}
SIZE = N;
}
public void union(int p, int q){
int x = find(p);
int y = find(q);
if (x == y) return;
for (int i = 0; i < union.length; i++){
if (union[i] == y) union[i] = x;
}
SIZE --;
}
public int find(int p){
return union[p];
}
public boolean connected(int p, int q){
return find(p) == find(q);
}
public int count(){
return SIZE;
}
public static void main(String[] args) {
In in = new In("./data/tinyUF.txt");
int N = in.readInt();
UF uf = new UF(N);
for (int i = 0; i < N; i++){
int p = in.readInt();
int q = in.readInt();
if (uf.connected(p, q)) continue;
uf.union(p,q);
System.out.println(p + " " + q);
}
System.out.println(uf.count() + " components");
}
}
关键在于union中的代码,为了维护元素所属的集合,在合并集合时:
p集合 <p1,p2>
q集合 <q1,q2,q3,q4,q5,a6>
union(p2,q1)操作
需要更新q集合中的每个元素,把它们对应的值改为p。
在代码实现中更加糟糕,需要遍历整个数组一次,所以:
union操作复杂度:O(n)
find操作复杂度: O(1)
一种基于数组的扁平结构,虽然find非常快,但对于合并操作真的是太糟糕了,可不可以加快合并?
在union操作中,为了维护这种扁平结构,需要循环遍历一次数组,这种操作相当费时。熟悉树的话,我们知道,对两棵树的合并相当简单,只要把一棵树依附到某个结点上,就能合并成一棵更大的树。
而对于任何子结点而言,如果我们能追根溯源到根结点,那么就认为这些结点都属于同一棵树,这意义巨大,同一棵树我们即可表示为同一集合,因为任何结点在这棵树中的归属一致。(通过find手段找到同根)
所以quick-union的合并思路和树的合并一个道理,union(p,q),p和q可以分别表示在存在于某棵树的两个中间结点,找到它们的根结点后,把一棵根结点树并到另一个根结点的孩子上。
嗯,数组可以用来表示森林,在堆中我们还知道数组可以表示成严格的完全二叉树。可见数组不仅仅是数组啊!
代码如下:
public void union(int p, int q){
int pid = find(p);
int qid = find(q);
if (pid == qid) return;
union[qid] = pid;
SIZE--;
}
public int find(int p){
while (p != union[p]){
p = union[p];
}
return p;
}
在平均情况下,union操作和find操作已经相当不错了,起码它们的时间复杂度为树的高度。可以参看《算法》P147页的时间复杂度分析。
但森林的构建非常依赖于输入union操作的顺序,在最坏情况下,可能会出现深度为N的一棵树,此时它的find操作就退化成了O(n)O(n),而union依赖find,也成了O(n)O(n),与其这样还不如再做点优化,稳定树的生长深度。
在最坏情况下,quick-union的深度即为结点数。这是因为在合并操作时,总是把大树依附在小树的结点上。所以为了规避上述这种情况,一种可行的方案就是把当遇到大树依附小树的情况,进行反向操作,让小树依附在大树上。
代码如下:
public class WeightedQuickUnionUF {
int[] id;
int[] sz;
int count;
public WeightedQuickUnionUF(int N){
count = N;
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
for (int i = 0; i < N; i++) sz[i] = 1;
}
public void union(int p, int q){
int pid = find(p);
int qid = find(q);
if (pid == qid) return;
if (sz[pid] < sz[qid]){
id[pid] = qid;
sz[qid] += sz[pid];
}
else{
id[qid] = pid;
sz[pid] += sz[qid];
}
count --;
}
public boolean connect(int p, int q){
return find(p) == find(q);
}
public int find(int p){
while (p != id[p]){
p = id[p];
}
return p;
}
public int count(){
return count;
}
public static void main(String[] args) {
In in = new In("./data/largeUF.txt");
int N = in.readInt();
UF uf = new UF(N);
for (int i = 0; i < N; i++){
int p = in.readInt();
int q = in.readInt();
if (uf.connected(p, q)) continue;
uf.union(p,q);
//System.out.println(p + " " + q);
}
System.out.println(uf.count() + " components");
}
}
一开始我以为sz是用来记录当前集合的高度,但不然,它记录的是当前集合的个数。这点很神奇,当把集合个数小的(小树)合并到集合个数大的大树上时,它就能规避最坏的情况。
对我来说有两点疑问:
要回答第一个问题,先得解决第二个问题,第二个问题比较简单。出现最坏情况的原因在于每当进行union操作时,树的深度就+1,树深度+1何时会出现?当且仅当大树依附在小树上,此时树的深度一定更新为1+大树深度
,因为小树深度<大树深度,所以合并操作导致树的高度变大。
我们的目标是尽量维持树的深度,如小树树高为3,大树树该为5,那么我们可以让小树依附在大树上,此时整棵树的高度没有增加依旧为5。
那为什么用元素个数来衡量树高同样可以保证算法正确呢?
归纳假设,在初始时,所有结点自成一派,元素个数为1,高度也为1,保证了find的高效性。
假设size小的集合,树的高度也较小,那么进行一轮合并得到新的集合时,高度不会增加。所以只要按照这种顺序更新,即能规避最坏情况。