What is concurrent search set? Are you still worried about it? In fact, it is a problem of connected graph, which is not so difficult to understand

Union checking set

analysis

Union checking set , A special data structure （ Its logical structure is also a “ Trees ”, There is a unique root node , Any number of child nodes ）, It is special in that it defines only two data operations （ Find and merge ）. This is used to solve connectivity problems , lookup （find）： Is to find whether any two nodes are connected , Is whether there is a common ancestor （ The process of a node finding its parent node , Search layer by layer ）. Merge （union）： Merge the nodes of two different sets together .
When I first saw and looked up the word set , Thought it was an algorithm . In fact, it can also be said to be an algorithm （ A special operation on the tree problem ）, But the code implementation of this algorithm usually needs to define two functions ：find（） and union（）

I defined a parent[n] Array , The array subscript is the number of each node , The stored value is the parent node of each node


These connected points are also called a packet ,find The function is to find nodes , If the subscript and value are the same, it means that the node is the ancestor node .

Code

public class UF {
    
    private int[] items;
    private int count;

    public UF(int n){
    
        this.count=n;
        items=new int[n];
        // It is specified that the index subscript is the value of each position during initialization 
        // This value represents the group 
        // That is to say, during initialization n It represents the number of groups 
        for (int i = 0; i < n; i++) {
    
            items[i]=i;
        }
    }
    public int getCount(){
    
        return count;
    }

    // The root identifier of the group where the element is located 
    public int getRootGroup(int p){
    
        while (p != items[p]) {
    
            p = items[p];
        }
        return p;
    }
    
    // Determine whether two points are in the same group 
    public boolean connected(int p,int q){
    
        return getRootGroup(p)==getRootGroup(q);
    }


    public void unioned(int p,int q){
    
        int pgroup = getRootGroup(p);
        int qgroup= getRootGroup(q);
        if (pgroup==qgroup){
    
            return;
        }
        items[pgroup]=qgroup;
        count--;
    }
}
class Test{
    
    public static void main(String[] args) {
    
        UF uf = new UF(5);
        System.out.println(" Before grouping :"+uf.getCount());
        uf.unioned(1,2);
        System.out.println(" After grouping :"+uf.getCount());
    }
}

In the previous code , There are still some problems , We use a tree structure on the storage of a reachable link , So it is better to traverse the chain than to traverse directly , If you want to merge two trees , It is also lower than the height of merging two chains directly . But we can also optimize , As you can see from the previous code , When we merged , In fact, the height of the tree is not taken into account , It is very likely that the height of the tree is the result of the addition of two trees , But because the nodes of the tree are forked , So we can merge short trees into tall trees , So the height of the last tree is the height of the tallest tree , Instead of adding two trees .
Actually, it's very simple , You only need to initialize the array , Save a copy of the height of each node :

    public void unioned(int p,int q){
    
        int pgroup = getRootGroup(p);
        int qgroup= getRootGroup(q);
        if (pgroup==qgroup){
    
            return;
        }
        // If p The height ratio of q Low height of 
        // Then the higher node should be used as the root node 
        if (highs[pgroup]<highs[qgroup]){
    
            items[pgroup]=qgroup;
        }else
            items[qgroup]=pgroup;

        count--;
    }

Unimpeded works

Please look at the picture , Join a 20 Cities , There are seven roads that have been built , The following seven groups of data represent the two cities that have been built , How many roads must be built to connect all the cities ?
This problem can be solved skillfully by using and searching sets , We know , If the merge set ends count The value of is 1, That means there is only one group in the array , That is, all nodes are connected .
So we just need to call the seven groups of data unioned Method , Merge into a group , After that, the remaining count-1 Is the road to be built .

        UF uf = new UF(20);
        System.out.println(" Before grouping :"+uf.getCount());
        uf.unioned(0,1);
        uf.unioned(6,9);
        uf.unioned(3,8);
        uf.unioned(5,11);
        uf.unioned(2,12);
        uf.unioned(6,10);
        uf.unioned(4,8);
        int count=uf.getCount()-1;
        System.out.println(" The road to be built remains :"+count); //12