Joint search set of data structure and algorithm (Disjoint Set)
Recognize and search the set
Many people will feel strange to the joint query set (Disjoint Set), have never heard of it or don't know it very well. In fact, parallel query set is a very efficient data structure. The implementation is simple, but all elements uniformly follow a law, so it makes things efficient.
For the definite meaning, the encyclopedia defines it as follows:
Union query set is a tree data structure, which is used to deal with the merging and query of some disjoint sets. It is often represented by forest in use.
And the basic idea of search set analysis is initialization. Each forest is independent. Usually expressed as an array, each value is initially - 1. Each is a root
(a, b) operation. a. B merge two sets. Note that a here is not the combination of a and B, but the combination of a and B. This leads to some situations: if a and B are independent (not merged with others), then a directly points to B (or B points to a), that is, data [a] = B; At the same time, in order to show how many there are in this set, B of - 1 is - 1 again That is, data [b] = - 2 Indicates that there are | - 2 nodes with B as the father.
If there is a set (maybe there is a father, maybe he is the root), then of course we can't directly operate on a and B (because a and B may already point to others.) Then we can only operate on the ancestors of a and B. Because the ancestors of a and B do not point (that is, negative data indicates size). Then they first add one negative value to the other. In addition, this value should become the one pointing to, indicating the connection.
You may have questions about the above:
How to check whether a and B are in a set? To check whether a node is in a collection, you only need to check whether the results of the node root ancestors are the same. Because only the value of the root is negative, while others are positive, indicating the element pointed to. So just keep looking until it is not a positive number for comparison! a. B merges, is it the ancestor of a merges on the ancestor of B, or the ancestor of B merges on a? There are two situations here, and this choice is also very important. You should understand that if the height of the tree is + 1, the efficiency of the whole element query will be reduced!
Therefore, we usually point to the big tree (or the low tree points to the high tree), which can increase the query efficiency!
Of course, you need to choose and consider your own height and quantity.
Other path compression?
Each query, from bottom to top. When we call recursion, we can compress the path by the way, because we only need to find an element up to its ancestor, so when it is close to its ancestor, the next query will be fast. And the cost of compressing the path is not big!
code implementation
And the implementation of search set is relatively simple, directly paste the code!
package 并查集不想交集合;
import java.util.Scanner;
public class DisjointSet {
static int tree[]=new int[100000];//假设有500个值
public DisjointSet() {set(this.tree);}
public DisjointSet(int tree[])
{
this.tree=tree;
set(this.tree);
}
public void set(int a[])//初始化所有都是-1 有两个好处，这样他们指向-1说明是自己，第二，-1代表当前森林有-（-1）个
{
int l=a.length;
for(int i=0;i<l;i++)
{
a[i]=-1;
}
}
public int search(int a)//返回头节点的数值
{
if(tree[a]>0)//说明是子节点
{
return tree[a]=search(tree[a]);//路径压缩
}
else
return a;
}
public int value(int a)//返回a所在树的大小（个数）
{
if(tree[a]>0)
{
return value(tree[a]);
}
else
return -tree[a];
}
public void union(int a,int b)//表示 a，b所在的树合并
{
int a1=search(a);//a根
int b1=search(b);//b根
if(a1==b1) {System.out.println(a+"和"+b+"已经在一棵树上");}
else {
if(tree[a1]<tree[b1])//这个是负数，为了简单减少计算，不在调用value函数
{
tree[a1]+=tree[b1];//个数相加 注意是负数相加
tree[b1]=a1; //b树成为a的子树，直接指向a；
}
else
{
tree[b1]+=tree[a1];//个数相加 注意是负数相加
tree[a1]=b1; //b树成为a的子树，直接指向a；
}
}
}
public static void main(String[] args)
{
DisjointSet d=new DisjointSet();
d.union(1,2);
d.union(3,4);
d.union(5,6);
d.union(1,6);
d.union(22,24);
d.union(3,26);
d.union(36,24);
System.out.println(d.search(6)); //头
System.out.println(d.value(6)); //大小
System.out.println(d.search(22)); //头
System.out.println(d.value(22)); //大小
}
}
package 并查集不想交集合;import java.util.Scanner;public class DisjointSet {static int tree[]=new int[100000];//假设有500个值public DisjointSet() {set(this.tree);}public DisjointSet(int tree[]) {this.tree=tree;set(this.tree);}public void set(int a[])//初始化所有都是-1 有两个好处，这样他们指向-1说明是自己，第二，-1代表当前森林有-（-1）个{int l=a.length;for(int i=0;i<l;i++){a[i]=-1;}}public int search(int a)//返回头节点的数值{if(tree[a]>0)//说明是子节点{return tree[a]=search(tree[a]);//路径压缩}elsereturn a;}public int value(int a)//返回a所在树的大小（个数）{if(tree[a]>0){return value(tree[a]);}elsereturn -tree[a];}public void union(int a,int b)//表示 a，b所在的树合并{int a1=search(a);//a根int b1=search(b);//b根if(a1==b1) {System.out.println(a+"和"+b+"已经在一棵树上");}else {if(tree[a1]<tree[b1])//这个是负数，为了简单减少计算，不在调用value函数{tree[a1]+=tree[b1];//个数相加 注意是负数相加tree[b1]=a1; //b树成为a的子树，直接指向a；}else{tree[b1]+=tree[a1];//个数相加 注意是负数相加tree[a1]=b1; //b树成为a的子树，直接指向a；}}}public static void main(String[] args){DisjointSet d=new DisjointSet();d.union(1,2);d.union(3,4);d.union(5,6);d.union(1,6);d.union(22,24);d.union(3,26);d.union(36,24);System.out.println(d.search(6));//头System.out.println(d.value(6)); //大小System.out.println(d.search(22));//头System.out.println(d.value(22)); //大小}}Conclusion parallel query is a simple but efficient data structure. Often encountered in collections. If it is not adopted and collected, the efficiency of traditional violence is too low to be adopted. In addition, parallel search set is also widely used in maze games. Here is an opportunity to introduce how to use parallel search set to realize a maze game.
summary
The above is the combined search set (Disjoint Set) of data structure and algorithm introduced by Xiaobian. I hope it will be helpful to you. If you have any questions, please leave me a message and Xiaobian will reply to you in time. Thank you very much for your support to our website! If you think this article is helpful to you, welcome to reprint, please indicate the source, thank you!