数据结构笔记总结(10.3)Quick Union

Quick Union

上一节我们实现了并查集的一种思路,使用数组进行模拟得到一种结果,叫做Quick Find,对于查找这种操作是非常快的。

标准情况下并查集的实现是通过Quick Union这种实现思路。

实现思路

将每一个元素看做是一个节点,节点之间相连接形成一棵树的结构,不过这棵树结构和之前所学的树结构都是不同的,并查集中的树结构是孩子指向父亲的。

在这里有一个节点3,如果节点3和节点2连在一起,连接方式是3这个节点指向2这个节点,2其实是整棵树的根节点,对于2来说,由于它是根节点,它也有一个指针指向自己。

这种情况下,节点1所代表的元素要和节点3所代表的元素合并,合并操作是怎么做的呢?实际上就是让1对应的指针指向3所在的这颗树的根节点,也就是让1指向2。

在并查集中可能存在一棵树(根节点为5的树,6和7为孩子节点都指向5),现在想让7这个元素和2这个元素合并,需要把7所在的根节点也就是5这个节点去指向2这个节点。

这就是我们实际实现并查集的思路。可以想象一下具体的存储所发生的变化,观察图可以看到,每一个节点其实只有一个指针,也就是只会指向另外一个元素,关于这个指针的存储依然可以使用数组的方式。

以10个元素为例的话,并查集开始就是这个样子,每一个节点都是根节点,指向自己,所以严格的来说并查集不是一棵树结构,而是一个森林。

森林就是里面有很多树,初始的情况下,现在我们这个森林中就有十棵树,每棵树都只有一个节点。

现在如果我们要进行union(4,3)这个操作,我们应该怎么做?其实就是将4这个节点它的指针去指向3这个节点就好了,数组中反应出来其实就是让parent(4)=3,这就代表4这个节点指向3这个节点。

下面如果我们再进行union(3,8)这个操作,让3这个节点指向8这个节点,数组中反应出来其实就是让parent(3)=8

如果再进行union(6,5),原理相同,依次类推……

再进行union(9,4),这里就有一个查询操作了,就要看一下4这个节点所在的根节点是谁呢?这个查询过程其实就是4指向3,3指向8,而8自己指向8,说明8是一个根节点,就找到了4的根节点是8,下面让9这个节点指向8这个节点就好了。

接下来依次进行union(2,1),union(5,0),union(7,2),union(6,2)

这就是我们并查集真正的实现方式。

代码实现

// 我们的第二版Union-Find
public class UnionFind2 implements UF {

    // 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树
    // parent[i]表示第一个元素所指向的父节点
    private int[] parent;
    private int size;  // 数据个数

    // 构造函数
    public UnionFind2(int size){

        parent = new int[size];
        this.size = size;
        // 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
        for( int i = 0 ; i < size ; i ++ )
            parent[i] = i;
    }

    @Override
    public int getSize(){
        return size;
    }

    // 查找过程, 查找元素p所对应的集合编号
    // O(h)复杂度, h为树的高度
    private int find(int p){
        if(p < 0 && p >= size)
            throw new IllegalArgumentException("p is out of bound.");

        // 不断去查询自己的父亲节点, 直到到达根节点
        // 根节点的特点: parent[p] == p
        while(p != parent[p])
            p = parent[p];
        return p;
    }

    // 查看元素p和元素q是否所属一个集合
    // O(h)复杂度, h为树的高度
    @Override
    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }

    // 合并元素p和元素q所属的集合
    // O(h)复杂度, h为树的高度
    @Override
    public void unionElements(int p, int q){

        int pRoot = find(p);
        int qRoot = find(q);

        if( pRoot == qRoot )
            return;

        parent[pRoot] = qRoot;
    }
}

源码下载

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

导航目录

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

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

Leave a Reply

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

立即加入 了解更多