Java collection extension series (a) | figure framework Java collection extension series (2) | index of Java collection extended series (3) | and check
1. What is a parallel search set
First of all, a look-up set is a collection a data structure that has two main operations
- Union: To combine two disjoint sets into a single set.
- Find: Determines whether two elements are in the same collection.
It is mainly used to deal with the problems of merging disjoint sets and judging connections.
2, and search set can do
- Identify connectivity issues (social networks, relationships)
- Recent common ancestor
- percolation
- The image processing
- Equivalence of finite state automata
- Hinley-milner’s polymorphic type inference
- Kruskal’s minimum spanning tree algorithm
- Games (Go, hexadecimal)
- The equivalence of compiled statements in Fortran
2, and check the set implementation structure
The structure of a parallel set is a bit like a tree, except that unlike a tree, Pointers point to the parent node. And there will be multiple trees in it. The following figure
3. Algorithm principle
3.1 Union
That is, two nodes are merged into the same collection. Suppose you have two nodes A and B, and generally you either add A to B, or you merge B to A. The parent pointer of the root node of A points to the root node of node B. However, in order to maintain the balanced height of the tree structure, the sum of the shorter node tree is generally merged into the higher node tree.
As shown in the figure below, to merge G and B, first find the root nodes A and E of G and B, and then point the parent pointer of E to A to complete the merger.
3.2. Find
That is, to determine whether two nodes are related, use the parent pointer to continuously look up the root node of the node, and then determine whether the root nodes of the two nodes are the same. If they are the same, it means they belong to the same set, and vice versa.
Although finding the root node is usually a very simple algorithm, in order to optimize performance and reduce the depth of each upward search, path compression is usually carried out in the process of finding the root node.
In the process of compression path, if it is found that the parent node is not the root node in the process of upward search, the parent pointer points to the grandfather node, and then directly jumps to the grandfather node for next judgment, and so on. When the root node is traversed, the entire path tree becomes very short, greatly reducing the depth of the search.
4. Code implementation
/** **@author burukeyou
*/
public class UnionFind<T> {
//parent[I] = x, indicating that node I points to the parent node x
private int[] parent;
// rank[I] indicates the number of layers represented by the set with root I. It is used primarily as a reference when merging collections and does not represent 100% accuracy
private int[] rank;
private Integer nodeKeyIndex = -1;
// Check the existing nodes of the set
private final Set<T> nodeSet = new HashSet<>();
// Map< node Key, actual node >
private final Map<Integer,T> keyNodeMap = new HashMap<>();
// Map< actual node, node Key>
private final Map<T,Integer> nodeKeyMap = new HashMap<>();
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
// Each parent[I] points to itself, indicating that each element is a collection of its own
for( int i = 0 ; i < size ; i ++ ){
parent[i] = i;
rank[i] = 1; }}public int getSize(a) {
return parent.length;
}
// Find the root node of the cur node
private int findRootNode(int cur) {
if(cur < 0 || cur >= parent.length){
throw new IllegalArgumentException("cur Index Out Of bounds");
}
// When the parent pointer points to itself, it is the root node
while(cur ! = parent[cur]){// Compress path, pointing to grandpa node, and so on
parent[cur] = parent[parent[cur]];
// Update the pointer to the current iteration
cur = parent[cur];
}
return cur;
}
// Assign a unique Key to a new node
private Integer distributeNodeKey(T node){
if(! nodeSet.contains(node)){ nodeSet.add(node); nodeKeyIndex++; keyNodeMap.put(nodeKeyIndex,node); nodeKeyMap.put(node,nodeKeyIndex); }return nodeKeyMap.get(node);
}
// Check whether elements X and y belong to a collection
public boolean isConnected(T x , T y){
Integer xKey = nodeKeyMap.get(x);
Integer yKey = nodeKeyMap.get(y);
if (xKey == null || yKey == null) {// If either one is empty, it means that the set is not added
return false;
}
// Check whether the root node is the same
return findRootNode(xKey) == findRootNode(yKey);
}
public void union(T x, T y) {
Integer xKey = distributeNodeKey(x);
Integer yKey = distributeNodeKey(y);
union(xKey,yKey);
}
// Merge the set of elements x and y,
private void union(int x, int y) {
int xRoot = findRootNode(x);
int yRoot = findRootNode(y);
if(xRoot == yRoot){
// It already belongs to the same group and does not need to be merged
return;
}
// merge the lower rank set into the higher rank set
if(rank[xRoot] < rank[yRoot]){
// When low depth is aggregated to high depth tree, direct the low depth root node to the root node of the high depth tree
parent[xRoot] = yRoot;
}else if (rank[xRoot] > rank[yRoot]){
/ / same as above
parent[yRoot] = xRoot;
}else {
// If the depth is the same, x is merged into y. And then we add 1 to the y tree
parent[xRoot] = yRoot;
rank[yRoot] += 1; }}}Copy the code5. Test cases
- Use the following social networks to determine whether or not two people are related
// Create and query the set
UnionFind<String> unionFind = new UnionFind<String>(30);
/ * suppose there is network Xiao Ming -- -- -- -- -- the small white -- -- -- -- -- two dogs | / small new jack Bauer - - zhang SAN li si * /
unionFind.union("Xiao Ming"."White");
unionFind.union("White"."Small new");
unionFind.union("White"."The dog");
unionFind.union("The dog"."Zhang");
unionFind.union("Zhang"."Bill");
// Judge whether Xiao Xin and Zhang SAN are indirect friends
boolean connected = unionFind.isConnected("Small new"."Zhang");
// Judge whether Xiao Xin and Xiao Qiang are indirect friends false
boolean connected1 = unionFind.isConnected("Small new"."Small strong");
System.out.println();
Copy the code