并查集系列之「路径压缩( path compression ) 」

并查集的路径压缩

一、介绍

并查集里的 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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!