First, let’s look at two path compression pictures:
Union-find Sets is a very delicate and practical data structure, which is mainly used to deal with the merge problem of some non-intersecting sets. Some common uses include connecting subgraphs, Kruskal algorithms for finding the minimum spanning tree, and Least Common Ancestors (LCA).
When using and looking up a set, first there will be a set of disjoint dynamic sets S={S 1 ,S 2 ,⋯,S k } , which generally uses an integer to represent an element in the set.
Each set may contain one or more elements, and an element in the set is selected as a representative. It is not important to care which elements are contained in each set, and it is not important to care which element is selected as the representative. What we care about is that for a given element, we can quickly find the set (representation) where this element is located, and merge the sets where the two elements are located, and the time complexity of these operations is constant.
There are three basic operations for checking and collection:
makeSet(s): Create a new and search set, which contains s single-element sets.
unionSet(x, y): merges the sets where element x and element y are located, and requires that the sets where x and y are located do not intersect, and if they intersect, they do not merge.
find(x): Find the representative of the set where element x is located. This operation can also be used to determine whether two elements are in the same set. Just compare their respective representatives.
package com.dataStructure.union_find;// Our fifth edition Union-Findpublic class UnionFind5 { // rank[i] represents the number of layers of the tree represented by a set rooted by i// In subsequent code, we will not maintain the semantics of rank, that is, the value of rank may not be the layer value of the tree during path compression.// This is also the reason why our rank is not called height or depth. It is just a standard for comparison private int[] rank; private int[] parent; // parent[i] represents the parent node pointed to by the i-th element private int count; // Number of data// Constructor public UnionFind5(int count){ rank = new int[count]; parent = new int[count]; this.count = count; // Initialization, each parent[i] points to itself, indicating that each element forms its own set for( int i = 0 ; i < count ; i ++ ){ parent[i] = i; rank[i] = 1; } } // Search process, find the set number corresponding to element p// O(h) complexity, h is the height of the tree private int find(int p){ assert( p >= 0 && p < count ); // path compression 1 while( p != parent[p] ){ parent[p] = parent[parent[p]]; p = parent[p]; } return p; // path compression 2, recursive algorithm// if( p != parent[p] )// parent[p] = find( parent[p] );// return parent[p]; } // Check whether element p and element q belong to a set// O(h) complexity, h is the height of the tree public boolean isConnected( int p , int q ){ return find(p) == find(q); } // Merge the set to which element p and element q belongs// O(h) complexity, h is the height of the tree public void unionElements(int p, int q){ int pRoot = find(p); int qRoot = find(q); if( pRoot == qRoot ) return; //Judge the merge direction based on the different number of elements in the tree where the two elements are located// Merge a set with fewer elements onto a set with more elements if( rank[pRoot] < rank[qRoot] ){ parent[pRoot] = qRoot; } else if( rank[qRoot] < rank[pRoot]){ parent[qRoot] = pRoot; } else{ // rank[pRoot] == rank[qRoot] parent[pRoot] = qRoot; rank[qRoot] += 1; // At this time, I maintain the value of rank} }}Summarize
The above is all the detailed explanation of the path compression code in this article about Java programming implementation and collection. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!