并查集 Union Find

并查集 Union Find

目录

​​第一种基础待优化的实现方式​​

​​第二种基于节点方式的优化实现方法，​​

​​第三种基于根节点的子节点数量的优化实现​​

​​第四种基于rank的优化实现​​

​​第五种路径压缩优化方式实现​​

并查集是一种不一样的数据结构，主要解决查找集合中元素之间是否连接

并--即表示合并，连接，，查---即表示查找

第一种基础待优化的实现方式

#pragma once//将UnionFind放到UF1命名空间内 namespace UF1 { class UnionFind { private: int *data; int count; public: UnionFind(int n) { data = new int[n]; count = n; for (int i = 0; i < n; i++) { data[i] = i; } } ~UnionFind() { delete[]data; } //查找p对应的值 int find(int p) { assert(p >= 0 && p < count); return data[p]; } //判断p,q是否相连 bool IsConect(int p, int q) { return find(p) == find(q); } //将两个元素并在一起,不是将两个并在一次，必须得从头遍历一次，保证跟其他并在一起 void UnionElement(int p, int q) { if (find(p) != find(q)) { for (int i = 0; i < count; i++) { if (data[i] == data[p]) data[i] = data[q]; } } } //返回并查集的大小 int size() { return count; } //输出所有并查集中元素的值 void out() { for (int i = 0; i < count; i++) { cout << data[i] << " "; } } };} void TestUnion(int n) { //利用当前的时间作为随机的种子，进行设置 包含#include srand(time(NULL)); UF1::UnionFind uf = UF1::UnionFind(n); clock_t startTime = clock(); for (int i = 0; i < n; i++) { //产生[0,n)的随机数 int a = rand() % n; int b = rand() % n; uf.UnionElement(a, b); } for (int i = 0; i < n; i++) { int a = rand() % n; int b = rand() % n; uf.IsConect(a,b); } uf.out(); clock_t endTime =clock(); cout << "UF1， " << 2 * n << "ops " << double(endTime - startTime) / CLOCKS_PER_SEC << " S"; }

上述的实现方法，在并操作时，需要遍历整个数组，耗时太大，

第二种基于节点方式的优化实现方法，

namespace UF2 { class UnionFind { private: int *data; int count; public: UnionFind(int n) { data = new int[n]; count = n; for (int i = 0; i < n; i++) { data[i] = i; } } ~UnionFind() { delete[]data; } //while方式实现寻找a元素的根 int findroot_(int a) { //查找，需要判断是否越界，不仅是上限，还有下限 assert(a >= 0 && a < count); while (data[a] != a) { a = data[a]; } return a; } //判断p,q是否相连 bool IsConect(int p, int q) { return findroot_(p) == findroot_(q); } void UnionElement(int p, int q) { //如果p，q的根的值不相等 int pid = findroot_(p); int qid = findroot_(q); if (pid != qid) { data[pid] = qid; } } //返回并查集的大小 int size() { return count; } //输出所有并查集中元素的值 void out() { for (int i = 0; i < count; i++) { cout << data[i] << " "; } } }; }

第三种基于根节点的子节点数量的优化实现

从第二种方法可以看出，我们总是随意的将两颗树的根节点合并在一起，并没有考量树的层数，这样很大概率会加深树的层数，增加查找时间，，

针对问题进行改进，在将根节点合并在一起之前，先考量两个根所包含的节点数，做到将节点少的那个树合并到节点多的那个树，减少查询时间

namespace UF3 { class UnionFind { private: //指向存放并查集数据的数组 int *data; //sz[i]表示元素i为根集合中元素的个数 int *sz; int count; public: UnionFind(int n) { data = new int[n]; sz = new int[n]; count = n; for (int i = 0; i < n; i++) { data[i] = i; //初始状态下都是指向自己，算1个指向 sz[i] = 1; } } ~UnionFind() { delete[]data; delete[]sz; } //while方式实现寻找a元素的根 int findroot_(int a) { //查找，需要判断是否越界，不仅是上限，还有下限 assert(a >= 0 && a < count); while (data[a] != a) { a = data[a]; } return a; } //判断p,q是否相连 bool IsConect(int p, int q) { return findroot_(p) == findroot_(q); } void UnionElement(int p, int q) { //如果p，q的根的值不相等 int pid = findroot_(p); int qid = findroot_(q); if (pid != qid) { //谁的树的个数少，谁挂在多的树上面，谁改变data[i] if (sz[pid] <= sz[qid]) { data[pid] = qid; //多的树的元素计数加上另外树的根的个数，并非加1 sz[qid]+=sz[pid]; } else //sz[pid] > sz[qid] { data[qid] = pid; //多的层数的树的元素计数加上另外树的根的个数，并非加1 sz[pid]+=sz[qid]; } } } //返回并查集的大小 int size() { return count; } //输出所有并查集中元素的值 void out() { for (int i = 0; i < count; i++) { cout << data[i] << " "; } } }; }

第四种基于rank的优化实现

rank[i]表示根节点为i的树的层数

namespace UF4 { class UnionFind { private: //指向存放并查集数据的数组 int *data; //rank[i]表示以第i个元素为根的层数 int *rank; int count; public: UnionFind(int n) { data = new int[n]; rank = new int[n]; count = n; for (int i = 0; i < n; i++) { data[i] = i; //初始状态下每个树都是只有一层 rank[i] = 1; } } ~UnionFind() { delete[]data; delete[]rank; } //while方式实现寻找a元素的根 int findroot_(int a) { //查找，需要判断是否越界，不仅是上限，还有下限 assert(a >= 0 && a < count); while (data[a] != a) { a = data[a]; } return a; } //判断p,q是否相连 bool IsConect(int p, int q) { return findroot_(p) == findroot_(q); } void UnionElement(int p, int q) { //如果p，q的根的值不相等 int pid = findroot_(p); int qid = findroot_(q); if (pid != qid) { //谁的层数少，谁挂在多的树上面，谁改变data[i]，但两个树的rank值都不发生改变 if (rank[pid] rank[qid]) { data[qid] = pid; } else// rank[pid] = rank[qid] { data[qid] = pid; //得到合并的树的rank值加1 rank[pid]++; } } } //返回并查集的大小 int size() { return count; } //输出所有并查集中元素的值 void out() { for (int i = 0; i < count; i++) { cout << data[i] << " "; } } }; }

第五种路径压缩优化方式实现

第一种路径压缩

第二种路径压缩

下列代码分别实现了两种路径压缩方式，一种是while形式，一种是递归形式，分别对应上图中的两种路径压缩，

namespace UF5 { class UnionFind { private: //指向存放并查集数据的数组 int *data; //rank[i]表示以第i个元素为根的层数 int *rank; int count; public: UnionFind(int n) { data = new int[n]; rank = new int[n]; count = n; for (int i = 0; i < n; i++) { data[i] = i; //初始状态下每个树都是只有一层 rank[i] = 1; } } ~UnionFind() { delete[]data; delete[]rank; } //while方式实现寻找a元素的根，并实现路径压缩， //int findroot_(int a) //{ // //查找，需要判断是否越界，不仅是上限，还有下限 // assert(a >= 0 && a < count); // // while (data[a] != a) // { // int a_data = data[a]; // //指向父亲节点，因为最后根节点会指向自己，所以不会越界 // data[a] = data[a_data]; // a = data[a]; // } // //返回a元素的根 // return a; //} //递归方式寻找a元素的根，并实现路径压缩， int findroot_(int a) { //查找，需要判断是否越界，不仅是上限，还有下限 assert(a >= 0 && a < count); if (data[a] != a) { data[a]=findroot_(data[a]); } //返回a元素的根 return data[a]; } //判断p,q是否相连 bool IsConect(int p, int q) { return findroot_(p) == findroot_(q); } void UnionElement(int p, int q) { //如果p，q的根的值不相等 int pid = findroot_(p); int qid = findroot_(q); if (pid != qid) { //谁的层数少，谁挂在多的树上面，谁改变data[i]，但两个树的rank值都不发生改变 if (rank[pid] < rank[qid]) { data[pid] = qid; } else if (rank[pid] > rank[qid]) { data[qid] = pid; } else// rank[pid] = rank[qid] { data[qid] = pid; //得到合并的树的rank值加1 rank[pid]++; } } } //返回并查集的大小 int size() { return count; } //输出所有并查集中元素的值 void out() { //先排序是为了更好的看出集合中有多少元素是并在一起的 quickSort(data, count); for (int i = 0; i < count; i++) { cout << data[i] << " "; } } }; }

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。