并查集系列之「思路优化」

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

一、介绍

在并查集的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;
             }
      };
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
刻意学习
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
118
粉丝
88
喜欢
173
收藏
244
排名:367
访问:2.6 万
私信
所有博文
社区赞助商