最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(10.2)Quick Find

    并查集的基本数据表示

    在并查集内部我们可以直接给每个数据做一个编号,这里0到9就表示10个不同的数据

    当然这是一种抽象的表示,10个编号可能是10个人或10辆车,但在并查集内部我们只存0到9这10个编号,它表示10个具体的元素。

    对于每一个元素并查集存储的是一个我们可以称之为叫做它所属于的集合的ID,比如编号为0到4这五个数据它们所对应的这个ID为0,编号为5到9的这五个数据它们所对应的ID为1,不同的ID值可以理解为不同的集合所对应的编号,换句话说,图中并查集中分成两个集合,其中0到4这五个元素在一个集合中,5到9这五个元素再另一个集合中。

    同理,如果并查集是这样,就意味着0、2、4、6、8这五个元素为同一个集合,剩下的为另一个集合。这样我们就很容易回答连接问题了,0和2这两个元素是相连接的,因为它们对应的ID相同。

    对于我们使用ID这样一个数组来存储数据是很容易回答isConnected这个问题的,只需要直接来看p和q对应的ID值是否一样就好了。我们将我们查询p或者q这些元素每个元素所对应的集合的ID是谁这个过程抽象成一个函数find,对于刚才描述的使用ID来存储每个数据所属的集合是谁的时候,只需要看find(p)是否等于find(q)

    当我们使用这种方式来操作的时候,复杂度为O(1)。这种方式是非常快速的,所以这种并查集方式通常也称作Quick Find。

    实现Quick Find查询操作

    // 我们的第一版Union-Find
    public class UnionFind1 implements UF {
    
        private int[] id;    // 我们的第一版Union-Find本质就是一个数组
        private int size;   // 数据个数
    
        public UnionFind1(int size) {
    
            id = new int[size];
            this.size = size;
    
            // 初始化, 每一个id[i]指向自己, 没有合并的元素
            for (int i = 0; i < size; i++)
                id[i] = i;
        }
    
        @Override
        public int getSize(){
            return size;
        }
    
        // 查找过程, 查找元素p所对应的集合编号
        // O(1)复杂度
        private int find(int p) {
            if(p < 0 && p >= size)
                throw new IllegalArgumentException("p is out of bound.");
    
            return id[p];
        }
    
        // 查看元素p和元素q是否所属一个集合
        // O(1)复杂度
        @Override
        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
    
        // 合并元素p和元素q所属的集合
        // O(n) 复杂度
        @Override
        public void unionElements(int p, int q) {
    
            int pID = find(p);
            int qID = find(q);
    
            if (pID == qID)
                return;
    
            // 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并
            for (int i = 0; i < size; i++)
                if (id[i] == pID)
                    id[i] = qID;
        }
    }
    

    源码下载

    [dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]

    导航目录

    [dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(10.2)Quick Find

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 127会员总数(位)
    • 3724资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 300稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级