并查集的路径压缩

一、介绍

并查集里的 find 函数里可以进行路径压缩，是为了更快速的查找一个点的根节点。对于一个集合树来说，它的根节点下面可以依附着许多的节点，因此，我们可以尝试在 find 的过程中，从底向上，如果此时访问的节点不是根节点的话，那么我们可以把这个节点尽量的往上挪一挪，减少数的层数，这个过程就叫做路径压缩。
通俗的说就是把find过程中“查找节点”的路劲变短，让find能更快的更高效。

二、逻辑

例如：find( 4 )
我们需要从下到上的找到根节点，当这条路劲很长，逻辑上花费的时间就会多一些

在路劲压缩的这个过程需要不断去查询自己的父亲节点, 直到到达根节点，而根节点的特点: parent[p] == p
不断的将节点4网上挪一挪使用：
parent[p] = parent[parent[p]];

最后就完成了路径压缩：

二、代码实现

#include<cassert>

using namespace std;
namespace UF4 {
    class UnionFind5 {
    private:
        // 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树
       // parent[i]表示第i个元素所指向的父节点  
       int *parent;
       int *rank;
       int count; //数据个数

    public:
          UnionFind5(int count) {
            parent = new int[count];
            rank = new int[count];
            this->count = count;
           //初始化
            for (int i = 0; i < count; i++) {
                   parent[i] = i;
            }
        }

        ~UnionFind5() {
            delete parent;
            delete rank;
  }

        // 查找过程, 查找元素p所对应的集合编号
       // O(h)复杂度, h为树的高度 
       int find(int p) {
            assert(p >= 0 && p <= count);
  // 不断去查询自己的父亲节点, 直到到达根节点
 // 根节点的特点: parent[p] == p  
            while (p != parent[p])
                parent[p] = parent[parent[p]];
                p = parent[p];
            return p;
 //递归算法
 //    if (p != parent[p])
 //          parent[p] = find(p); 
 //          return parent[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;

             if (rank[pRoot] > rank[qRoot]) {
                    parent[pRoot] = qRoot;
             }

            else if (rank[pRoot] < rank[qRoot]) {
                    parent[qRoot] = pRoot;
             }

            else {//rank[pRoot] == rank[qRoot]
                    parent[qRoot] = pRoot;
                    rank[qRoot] = +1;
            }
        }
    };
}

(图片来源：慕课网课程《算法与数据结构》)

本作品采用《CC 协议》，转载必须注明作者和本文链接