-
UnionFind(并查集)
UnionFind(并查集)
简单来说就是由孩子节点指向父亲节点形成的树，主要用于解决连接问题，判断网络中两节点的连接状态（即问两事物是否属于同一集合）。
并查集主要支持两个动作，即unionElements和isConnected。即将两个节点合并放入一个集合，判断两个节点是否属于同一集合。
下面给出并查集UF的接口实现：
//q,p抽象为两个节点id,具体p,q指向的是什么内容是随意的 class UF { public: virtual bool isConnected(int p, int q) = 0; virtual void unionElements(int p, int q) = 0; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
下面将给出不同版本的并查集实现，并不断递进优化
Quick Find
基于快速判断的思想，每个节点由数组来标记自己属于某个集合，初始时每个几点独立构成一个集合。要实现快速查找，简单的思想就是判断是否属于同于集合直接比较两节点的父亲节点是否相同，合并时遍历整个数组，将以节点1为父亲的所有节点的父亲改为节点二。
判断:O(1)
合并:O(n)
// Quick Find class UF1 : public UF { public: UF1(int size) { id.resize(size); for (int i = 0; i < size; ++i) { id[i] = i; } } bool isConnected(int p, int q) { return id[p] == id[q]; } void unionElements(int p, int q) { if (id[p] == id[q]) { return; } for (int i = 0; i < id.size(); ++i) { if (id[i] == p) id[i] == q; } } private: vector<int> id; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
Quick Union
基于快速合并的思想，定义一个find方法查找两节点的父亲，合并时直接通过find到的父亲来合并两棵树。h为树高，极端情况下可能都退化到O(n)
判断:O(h)
合并:O(h)
// QuickFind 孩子指向父亲的树 class UF2 : public UF { public: UF2(int size) { parent.resize(size); for (int i = 0; i < size; ++i) { parent[i] = i; } } bool isConnected(int p, int q) { return find(p) == find(q); } void unionElements(int p, int q) { int rootp = find(p); int rootq = find(q); parent[rootp] = parent[rootq]; } private: int find(int p) { while (parent[p] != p) { p = parent[p]; } return p; } vector<int> parent; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
基于size优化
基本思想是合并两棵树时，将节点少的树合并到节点多的树下面去，避免树过高而导致时间复杂度过高。所以引入一个rank数组来记录每个节点的树高（以该节点为根时）。h为树高，由于树高得到优化，一般不会退化到O(n)。
判断:O(h)
合并:O(h)
//基于size的优化 class UF3 : public UF { public: UF3(int size) { parent.resize(size); rank.resize(size); for (int i = 0; i < size; ++i) { parent[i] = i; rank[i] = 1; } } bool isConnected(int p, int q) { return find(p) == find(q); } void unionElements(int p, int q) { int rootp = find(p); int rootq = find(q); if (rank[rootp] < rank[rootq]) { parent[rootp] = parent[rootq]; rank[rootq] += rank[rootp];//更新parent为根节点的节点总数 } else { parent[rootq] = parent[rootp]; rank[rootp] += rank[rootq];//同时 } } private: int find(int p) { while (parent[p] != p) { p = parent[p]; } return p; } vector<int> parent; vector<int> rank; //以high[i]为根节点的树的元素个数 };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
基于Rank优化
继续优化树高，显而易见的是结点数多的树高度不一定就越大，rank记录的应该是以某节点为根时树的高度。在合并时维护树高即可
复杂度分析同UF3
//基于rank的优化 class UF4 : public UF { public: UF4(int size) { parent.resize(size); rank.resize(size); for (int i = 0; i < size; ++i) { parent[i] = i; rank[i] = 1; } } bool isConnected(int p, int q) { return find(p) == find(q); } void unionElements(int p, int q) { int rootp = find(p); int rootq = find(q); if (rank[rootp] < rank[rootq]) { parent[rootp] = parent[rootq]; // rank[rootq] += rank[rootp];//不用维护，树高并未改变 } else if (rank[rootp] > rank[rootq]) { parent[rootq] = parent[rootp]; // rank[rootp] += rank[rootq];//不用维护，树高并未改变 } else { parent[rootp] = parent[rootq]; rank[rootq]++; //树高+1 } } private: int find(int p) { while (parent[p] != p) { p = parent[p]; } return p; } vector<int> parent; vector<int> rank; //以high[i]为根节点的树的元素个数 };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
路径压缩优化1
要尽可能的压缩树高，则我们决定在每次合并是尽可能的使得树节点都合并到他的父亲的父亲节点上，进而进一步的缩减树高。到这里树高已经达到常规的logn的高度，且随着多次的合并，树高会不断降低。
特别说明一下rank,可见这里的rank已经不是确切的树高了，广义上来说他只是一种模糊的衡量树高的标准了。
复杂度分析同UF4,理论上来说更快了。
//路径压缩 class UF5 : public UF { public: UF5(int size) { parent.resize(size); rank.resize(size); for (int i = 0; i < size; ++i) { parent[i] = i; rank[i] = 1; } } bool isConnected(int p, int q) { return find(p) == find(q); } void unionElements(int p, int q) { int rootp = find(p); int rootq = find(q); if (rank[rootp] < rank[rootq]) { parent[rootp] = parent[rootq]; // rank[rootq] += rank[rootp];//不用维护 } else if (rank[rootp] > rank[rootq]) { parent[rootq] = parent[rootp]; // rank[rootp] += rank[rootq];//不用维护 } else { parent[rootp] = parent[rootq]; rank[rootq]++; //树高+1 } } private: int find(int p) { while (parent[p] != p) { parent[p] = parent[parent[p]]; //路径压缩，树高进一步优化 p = parent[p]; } return p; } vector<int> parent; vector<int> rank; //以high[i]为根节点的树的元素个数 };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
路径压缩优化2
最直接的我们想要每棵树最多有两层，即父亲和二者。这里运用递归，在每次find时将所有的子节点都接到最终find到的根节点上去。树高更低了。与上一个优化相比这里多了递归的开销，复杂度相差理论上不大。
//路径压缩 class UF6 : public UF { public: UF6(int size) { parent.resize(size); rank.resize(size); for (int i = 0; i < size; ++i) { parent[i] = i; rank[i] = 1; } } bool isConnected(int p, int q) { return find(p) == find(q); } void unionElements(int p, int q) { int rootp = find(p); int rootq = find(q); if (rank[rootp] < rank[rootq]) { parent[rootp] = parent[rootq]; // rank[rootq] += rank[rootp];//不用维护 } else if (rank[rootp] > rank[rootq]) { parent[rootq] = parent[rootp]; // rank[rootp] += rank[rootq];//不用维护 } else { parent[rootp] = parent[rootq]; rank[rootq]++; //树高+1 } } private: int find(int p) { //路径压缩到只有两层 if (p != parent[p]) { parent[p] = find(parent[p]); } return parent[p]; } vector<int> parent; vector<int> rank; //以high[i]为根节点的树的元素个数 };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
总结
并查集的复杂度比较难分析，总的来说判断和合并的复杂度都是O(log*n)级别（读作:log star n）。注意不是logn,这是一个趋近于O(1)的比O(1)大比O(logn)小的复杂度。
测试
//测试代码 //头文件 #include#include #include #include #include using namespace std; //... //合并和判断各进行optimes次操作耗费的时间，size为初始点的个数 long long testUF(UF *uf, int optimes, int size) { auto start = chrono::high_resolution_clock::now(); srand(time(0)); for (int i = 0; i < optimes; i++) { int p = rand() % size; int q = rand() % size; uf->unionElements(p, q); uf->isConnected(p, q); } auto end = chrono::high_resolution_clock::now(); auto dur = end - start; return dur.count(); } int main() { int optimes = 100000; int ufsize = 100000; // UF *uf1 = new UF1(ufsize); // UF *uf2 = new UF2(ufsize); UF *uf3 = new UF3(ufsize); UF *uf4 = new UF4(ufsize); UF *uf5 = new UF5(ufsize); UF *uf6 = new UF6(ufsize); //printf("UF1 cost time:%dms\n", testUF(uf1, optimes, ufsize) / 1000000);//10000次 //printf("UF2 cost time:%dms\n", testUF(uf2, optimes, ufsize) / 1000000);10000次 printf("UF3 cost time:%dms\n", testUF(uf3, optimes, ufsize) / 1000000);//100000次 printf("UF4 cost time:%dms\n", testUF(uf4, optimes, ufsize) / 1000000);//100000次 printf("UF5 cost time:%dms\n", testUF(uf5, optimes, ufsize) / 1000000);//100000次 printf("UF6 cost time:%dms\n", testUF(uf6, optimes, ufsize) / 1000000);//100000次 } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
测试结果：测试结果与机器及运行时各自因素有关，只能做初略比较展示
由于UF1,UF2比较耗时，故测试的是10000/10000
下面三个测试是100000/100000
并查集代码解题实践[leetcode]
后续补充链接
-
相关阅读:
golang 单个、多个分隔符和使用正则表达式 - 分割字符串
数据结构-线性结构-队列
磁盘空间占满导致confluence6.3不可用问题修复流程
靠云业务独撑收入增长大梁，微软仍然被高估？
【第三部分 | 移动端开发】2：流式布局
企业软件定制开发的重点是什么？|app小程序网站建设
【Python深度学习】Python全栈体系（三十三）
css div左右布局
关于git flow的一点思考
python-pandas用法大全
- 原文地址：https://blog.csdn.net/weixin_45730130/article/details/126373381
