union find的一些改善和完成剖析ITeye - AG环亚娱乐集团

union find的一些改善和完成剖析ITeye

2019-01-13 22:08:19 | 作者: 若云 | 标签: 完成,节点,元素 | 浏览: 324

    Union find是一种常用于调集各种操作的结构。首要包括有两个部分,一个是查找调集中是否包括有元素,别的一个是针对两个调集进行兼并。这儿的调集更多的是一种数学意义上的元素合集,在这么一个调集里没有重复的元素,可是依据元素之间的各种联系咱们将一些元素兼并到一个子集里,然后形成了上述的两个首要问题。在前面一篇图论相关的文章里现已评论了union find的两种常用完成。这儿针对它的一些优化进行细节评论。Union find在一些调集区分,图区分的使用问题中有比较多的使用。

 

union find的两种完成

    尽管在前面的文章里现已专门抽了章节叙述了union find的界说,这儿再做进一步的描绘。由于union find针对的是调集。而从数学的描绘来说,它们仅仅一组不重复的元素。从数据结构的视点来描绘的话,咱们有许多种挑选。比方linked list, array, set等等。所以在许多详细的完成里,针对不同的场景能够挑选不同的结构。咱们这儿针对一种比较简略的完成来评论。

    咱们知道,关于一个调集来说,最简略的办法就是界说成一个数组。里边每个下标对应调集里的每个元素,并且一开端的时分,数组里每个元素的值和下标值相同,表明它们是同一个标号。所以,针对咱们查找元素和兼并调集元素的时分,咱们有两种完成的战略。

简略元素替换

    依照这种办法,咱们每次兼并一个新的元素进来的时分,都要将本来调集里一切元素的值都修正为新并入元素的值。这样做的原因在于什么呢?由于咱们每次兼并一个元素之后,需求有一种办法来表明这么几个兼并在一起的元素。而关于这些兼并在一起的元素来说,咱们取他们中心哪个做代表并不重要,关键是咱们随意找到它们中心的某个元素就能断定它们地点的调集标识。

    所以,咱们这儿的战略就是每次将新并入的元素当作这个调集的仅有标识。这样做的优点就是完成起来很简略,当然,每次更新的时分基本上要扫描一遍整个调集。一个完好的完成如下:

public class UF {
 private int[] id;
 private int count;
 public UF(int n) {
 count = n;
 id = new int[n];
 for(int i = 0; i i++)
 id[i] = i;
 public int count() {
 return count;
 public boolean connected(int p, int q) {
 return find(p) == find(q);
 public int find(int p) {
 return id[p];
 public void union(int p, int q) {
 int pId = find(p);
 int qId = find(q);
 if(pId == qId) return;
 for(int i = 0; i id.length; i++)
 if(id[i] == pId) id[i] = qId;
 count--;
}

    它查找元素的时刻杂乱度十分低,只需O(1),而兼并调集元素的时分时刻杂乱度到达了O(N)。这种完成看起来还能够,就是感觉兼并的时分好像慢了一点,那么有没有办法使得兼并的操作快点呢?

 

代表元素兼并

    和前面归并元素的思路不同,这儿选用的是一种类似于树的层次结构。这儿的层次并不是在每个元素上面添加一个树那样的指针节点,而是在数组里,咱们假定每个下标的数值表明这个元素,那么这个下标对应的元素值比方说a[1],这儿1表明元素1,而a[1]能够表明1这个元素的父节点。依照这个思路,假如咱们将一个元素并入到一个调集的时分,咱们能够修正这个调集的代表元素,只需这个代表元素的值为这个并入的元素就能够了。所以关于一些独自的节点或许根节点来说的话,它应该满意一点,即它自身的值和下标值是持平的。

    依照这种思路,一个完成如下:

public class UF {
 private int[] id;
 private int count;
 public UF(int n) {
 if(n 0)
 throw new IllegalArgumentException();
 count = n;
 id = new int[n];
 for(int i = 0; i i++)
 id[i] = i;
 public int count() {
 return count;
 public boolean connected(int p, int q) {
 return find(p) == find(q);
 public int find(int p) {
 if(p 0 || p id.length)
 throw new IndexOutOfBoundsException();
 while(p != id[p])
 p = id[p];
 return p;
 public void union(int p, int q) {
 int pRoot = find(p);
 int qRoot = find(q);
 if(pRoot == qRoot)
 return;
 id[pRoot] = qRoot;
 count--;
}

    这种完成里,查找地点调集的代表元素需求遍历它的父节点,直到它和它的下标值相同。可是归并的时分只需修正一个元素的值就能够了。不过从最坏的状况来看,查找这个调集的根节点的时刻杂乱度就可能将近O(N)了。看来这个办法是使得归并的操作简略了,可是全体的时刻杂乱度并没有彻底降下去。

    那么还有没有什么办法能够改善呢?

 

    咱们知道,针对后边这个兼并的办法,它的问题就是在于当呈现一些特别的状况时,兼并的元素和它的父节点形成了一个线性表结构,每次要去查找都要将整个表遍历一遍。问题的中心就在这儿。假如有一种办法能够使得每个调集里从元素到根节点的间隔尽可能的短,那么咱们能够很好的改善功能。

 

weighted quick union

    这种办法就是在前面的办法上做了一个改善。咱们本来每次兼并调集的时分,都是固定的把一个元素的父节点设置为别的一个调集代表节点。咱们知道一个调集越大,它到每个叶节点的长度就越长。假如这个时分咱们再把这个大的调集的长度加长的话,只需求把它的根节点再往上延伸,也就是将它并入到别的一个调集里。而为了尽可能的确保它满足小,咱们能够在两个调调集并的时分判别一下它们的巨细,将小的并入到大的调集里,这样它的根途径长度就能够尽量坚持得比较短。

    依照这种思路,咱们完成的时分需求针对每个节点来界说以它为根节点的调集元素的多少。所以,咱们需求额定再添加一个数组,专门来记载这个信息。在每次归并比较的时分,直接比较这个对应的值就能够了。并且归并之后要相应修正归并后调集根节点对应的值。

所以现在完成能够改动如下:

public class WeightedQuickUnionUF {
 private int[] id;
 private int[] sz;
 private int count; //表明里边调集的个数
 public WeightedQuickUnionUF(int n) {
 count = n;
 id = new int[n];
 for(int i = 0; i i++) id[i] = i; //每个元素最开端将它的父节点设置为自身
 sz = new int[n];
 for(int i = 0; i i++) sz[i] = 1; //设置每个节点对应的调集巨细为1
 public int count() { return count; }
 public boolean connected(int p, int q) {
 return find(p) == find(q);
 public int oldFind(int p) {
 while(p != id[p]) p = id[p];
 return p;
 public void union(int p, int q) {
 int i = oldFind(p);
 int j = oldFind(q);
 if(i == j) return;
 // 判别每个调集元素的巨细,然后调整根节点对应的元素个数
 if(sz[i] sz[j]) { id[i] = j; sz[j] += sz[i]; }
 else { id[j] = i; sz[i] += sz[j]; }
 count--; 
}

    前面的完成代码里咱们添加了一个数组int[] sz来盯梢每个元素为根节点调集的巨细。然后每次兼并的时分判别两个调集的巨细,再将小的并入到大的调集里。

    依照前面的思路,咱们输入一组调集元素联系的时分,它们归并的进程如下图:

    在前面的一些输入对如3, 8和6 1的时分,都是小的调集被作为一个子节点兼并到了大的调集中。经过这种优化的办法,程序运转的时刻杂乱度能够到达O(logN)的作用。当然, 一般来说到了这一步,咱们现已到达了一个很好的成果。实际上咱们还有一个能够改善的当地,那就是path compression。

 

path compression

    关于前面的调集归并,它们很大一部分的时刻是花在经过一个节点去查找它的根节点。所以从一个节点到它的根节点间隔越短越好。在前面的完成中,咱们能够确保每个节点到根节点的间隔最多为logN。而假如咱们有机会对它们的间隔做进一步的紧缩呢?这就是path compression的关键。由于咱们每次要对两个调调集并的时分,都要经过find去查找它调集的根节点,假如每次咱们在查找的进程中一起调整它到根节点的间隔,使得它到根节点的间隔为1,这不是更好吗?

    所以,一种典型的紧缩作用应该如下图:

    当然,这种抱负的状况也和咱们输入的元素联系对有联系,后边会对这个联系做进一步的剖析。依照前面给出的这个紧缩思路,咱们要修正的当地关键在于find办法,所以一种递归的紧缩办法完成如下:

public int find(int p) {
 if(p != id[p]) 
 id[p] = find(id[p]);
 return id[p];
 }

   这种完成比较奇妙,能够将当时节点以及从它到根节点的一切元素都设置为直接指向根节点。第一次看这个代码的完成时还颇费了点功夫,由于这一层层的递归嵌套,有时分的确比较难让人了解。咱们能够依照如下的递归嵌套图来考虑:

    假定咱们有一个树结构的分支,从叶节点1一向到根节点4。 它们的次序如下:

 

1--- 2---- 3---- 4

1.p = find(1.p) --find(2)  
2.p = find(2.p)  --find(3) 
3.p = find(3.p) -- find(4)  x==3 4

    咱们假定p为指向父节点的值。那么如上面所描绘,每次求一个节点的父节点值的时分就需求递归到下一层,比方这儿求1.p,就需求求find(2),这样一向到find(4)。咱们知道find(4)回来的成果是4。所以依照递归回来的联系就能够知道3.p = find(4),所以得到find(3)的成果是4, 再顺次回来给find(2) = 4,这样一向到最后。所以这样就确保了从叶节点到根节点这个途径上一切的节点都指向了它的根节点,一起还把根节点的值给回来了。这种完成的思路比较简练,仅仅有的时分不太好懂。当然,咱们还能够依据前面的思路完成一个非递归版别的,就是选用一个数组来保存从叶节点到根节点的一切节点,然后将这儿一切的节点都直接指向根节点。代码的完成如下:

public int find(int p) {
 List Integer list = new ArrayList Integer 
 while(p != id[p]) {
 list.add(p);
 p = id[p];
 for(Integer i : list) {
 id[i] = id[p];
 return id[p];
}

    这个完成就没什么好再说的了。

    不过还有一个比较有意思的就是在网上还有一种写法,看似能够把一切从叶节点到根节点的元素都修正了,它的完成如下:

   

public int itFind(int p) {
 while(p != id[p]) {
 id[p] = id[id[p]];
 p = id[p];
 return p;
 }

     这部分代码细心剖析的话,会发现它仅仅把从当时叶节点到向上每两层的节点都指向自己的祖父节点。并不是一切的都指向了根节点。在树层次不深的时分这个问题还看不出来。有爱好的能够自己去画一下。

    还有一个需求阐明的就是,前面提到过,咱们结构的树和输入的数对也是有联系的。尽管前面的办法能够使得整个的途径得到紧缩,在某些状况下,仍是能够结构出最坏长度为logN的树来。比方说每次输入的数对都是两棵树的根节点,这样经过查找从叶节点到根节点来紧缩的作用就发挥不出来了。一个典型的输入如下:{ (1, 2), (3, 4) (5, 6) (7, 8), (1, 3), (5, 7), (1, 5)} 。这儿依照前面的思路得到的图如下:

第一轮归并:

第二轮归并:

第三轮归并

    这是一种比较特别的状况,尽管path compression的作用没有发挥出来,可是它能够确保最坏的状况下path的长度为logN。从概率的视点来说,究竟这样的状况是很少见的。

 

    调集的界说、查找和归并其实是一个比较值得深究的问题。尽管这儿的界说完成并不杂乱,可是结合一些优化手法的时分,仍是有许多细节值得注意的。别的,咱们有细心考虑过这种改善后的算法准确时刻杂乱度会有多少呢?书上给出的答案是ackerman函数的倒数。归于十分挨近常数的一个量级了。不过它的推导仍是十分费事,有时刻的话再针对这个深化评论评论。

 

Algorithms

Introduction to algorithms

http://stackoverflow.com/questions/12696803/weighted-quick-union-with-path-compression-algorithm
http://en.wikipedia.org/wiki/Disjoint-set_data_structure

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表AG环亚娱乐集团立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章