并查集的另一种实现思路(优化)

一、介绍

在并查集的Union( ) 中使用指针，将每一个元素看作是一个节点，并将每一个节点都指向一个节点(可以是其他节点或节点本身)即Quick Union；使用这种方法在后续可以更好的对并查集进行优化。

二、 Union的表示方法及逻辑

在Quick Find下的union时间复杂度为( O(n) )

将每一个元素看作是一个节点，如下图：

初始化一样，每一个元素是一个集合

并且每一个元素指向自己

下面我们将4，3连接( union(4, 3) )

再继续：将3，和8连接(union(3, 8) )

将6，5进行连接( union(6, 5) )

这里注意：我们将9，4连接( union(9, 4) )

我们是将9指向8节点(这样更优化)，在逻辑上就是9，和4连接上了

再看这里，同样的逻辑，将其中一方的根节点指向另一个的根节点

连接6，2 ( union(6, 2) )

连接后：

优化后的表示方法及逻辑就是这样。

三、代码实现

我先看union部分：

// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
void unionElments(int p, int q) {    //union在c++中是关键字  
    int pRoot = find(p);
    int qRoot = find(q);

    if (pRoot == qRoot)return;

     parent[pRoot] = qRoot;
}

下面是完整代码：

#include<cassert>
using namespace std;
namespace UF2 
{
    class UnionFind2 
    {
        private:
        // 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树 
        // parent[i]表示第i个元素所指向的父节点 
        int *parent;
        int count; //数据个数 
        public:UnionFind2(int count) 
        {
            parent = new int[count];
            this->count = count;
            //初始化 
            for (int i = 0; i < count; i++) 
            {
                parent[i] = i;
            }
        }
        //析构函数~ 
        UnionFind2() 
        {
            delete parent;
        }
        // 查找过程, 查找元素p所对应的集合编号 
        // O(h)复杂度, h为树的高度 
        int find(int p) {
            assert(p >= 0 && p <= count);
            // 不断去查询自己的父亲节点, 直到到达根节点 
            // 根节点的特点: parent[p] == p   
            while (p != parent[p])
                p = parent[p];
            return p;
        }
            // 查看元素p和元素q是否所属一个集合// O(h)复杂度, h为树的高度 
        bool isConnected(int p, int q) 
        {
            return find(p) == find(q);
        }
        // 合并元素p和元素q所属的集合// O(h)复杂度, h为树的高度   
        void unionElments(int p, int q) 
        {
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot == qRoot) return;
            parent[pRoot] = qRoot;}};
        }
    }
}