本文主要向大家介绍了【云计算】数据结构之并查集，通过具体的内容向大家展现，希望对大家学习云计算有所帮助。

public class MyUF5 implements MyUnionFind {
    //简单的并查集实现
    //添加属性 当前节点有多少个元素 初始值为1
    private int[] parent;
    private int[] rank;
    public MyUF5(int size){
        rank = new int[size];
        parent = new int[size];
        //初始化数组 假设 每个数组属于对应索引的组
        for(int i = 0;i=parent.length)
            throw new IllegalArgumentException("index erro");
        //递归找到根节点 并将根节点返回给路径上的所有对象
        if(id!=parent[id])
            //如果不是根节点 递归查找根节点
            parent[id]=find(parent[id]);
        //是根节点 返回根节点
        return parent[id];
    }
    @Override
    public int getSize() {
        return parent.length;
    }

    @Override
    public void unionE(int p, int q) {
        int pf=find(p);
        int qf = find(q);
        if(pf==qf)
            return;
        //判断谁的树深 将深度浅的指向深度深的
        if(rank[pf]rank[qf])
            parent[qf]=pf;
        else{
            //相等
            parent[pf]=qf;
            rank[qf]+=1;
        }

    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p)==find(q);
    }
}

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标大数据云计算大数据安全频道！