路径压缩
-------------------siwuxie095
路径压缩
基于size 的优化和基于 rank 的优化，主要都是针对 Union 操作
的优化，实际上，Find 操作其实也是可以优化的
Find 操作就是从一个节点开始，通过它的指向父亲的指针，不断
向上追溯，直至根节点，也就是寻找根的过程
在这个过程中，其实已经将从这个节点开始，一直到根节点的每
个节点，都遍历了一遍
之前所实现的Find 操作只是直接的遍历，没有做任何操作，但在
这个过程中，其实可以对节点做一些变化，让树的层数更少
具体方法：尝试着在执行Find 操作（自底向上，不断溯源）时，
如果没有找到根节点，就想办法把这些节点向上挪一挪，称这个
过程为路径压缩（Path Compression）
「即判断当前节点是否为根，如果不是（即没有找到），就把
以当前节点为根的子树整体向上挪，挪到当前节点的父亲的父亲
处，下次再判断当前节点的父亲（即原来的祖先）是否为根 …
相当于跳了一步，所以叫路径压缩」
假设存在并查集，如下：
如果要find( 4 )，发现 parent[4] = 3，而 ≠ 4，判断 4 不是根节点
1）在原来的Find 操作中，要继续向上找，判断 3 是不是根节点 …
2）而现在的路径压缩则是压缩一步，让 4 去连接它父亲的父亲，也
就是 2。此时，整棵树的层数就变少了，即被压缩了
注意：这里是先判断是否为根，如果 4 已经是根了，自然无须去连接
它父亲的父亲，直接返回即可。如果 3 已经是根了，因为 3 的父亲是
3，所以让 4 去连接它父亲的父亲，依然成立
下面要考察的就是 4 的父亲 2，即find( 2 )，这里没有考察 3，
相当于跳了一步
发现parent[2] = 1，而 ≠ 2，即 2 也不是根节点，继续路径压
缩，让 2 去连接它父亲的父亲，也就是 0
下面要考察的就是 2 的父亲 0，即find( 0 )，这里没有考察 1，
相当于又跳了一步
发现parent[0] = 0，即 0 就是根节点，返回 0 即可
在find( 4 ) 的过程中，成功把这颗树的根节点 0 返了回去，
同时，整棵树的层数也大大地减少了，这便是路径压缩
路径压缩还可以继续优化，最优的情况（理论上），能将整个路径
压缩成 2 层，所有的节点都指向一个根，如下：
「注意：这种理论上的优化，实际用时更长（主因：递归的开销）」
程序 1：路径压缩的实现
UnionFind.h：
|
#ifndef UNIONFIND_H #define UNIONFIND_H
#include <iostream> #include <cassert> using namespace std;
//并查集：Quick Union + rank + path compression namespace UF {
class UnionFind {
private: int* parent; int* rank; // rank[i]表示以i为根的集合所表示的树的层数 int count;
public: UnionFind(int count) { this->count = count; parent = newint[count]; rank = newint[count]; //在初始情况下，并查集里的元素，两两之间互不连接 for (int i = 0; i < count; i++) { parent[i] = i; rank[i] = 1; } }
~UnionFind() { delete []parent; delete []rank; }
int size() { return count; }
int find(int p) {
assert(p >= 0 && p < count);
// path compression 1 while (p != parent[p]) { //路径压缩 parent[p] = parent[parent[p]]; p = parent[p]; }
return p; }
bool isConnected(int p, int q) { return find(p) == find(q); }
void unionElements(int p, int q) {
int pRoot = find(p); int qRoot = find(q);
if (pRoot == qRoot) { return; }
//rank小的那棵树的根节点指向rank大的那棵树的根节点 if (rank[pRoot] < rank[qRoot]) { parent[pRoot] = qRoot; } else if (rank[qRoot] < rank[pRoot]) { parent[qRoot] = pRoot; } // rank[pRoot] == rank[qRoot] else { //可互换 parent[pRoot] = qRoot; rank[qRoot] ++; }
}
void show() { for (int i = 0; i < count; i++) { cout << i << " : " << parent[i] << endl; } } }; }
//路径压缩：在寻找根的时候，两步一跳，比原来的 Find 操作要快， //与此同时，如果下一次要寻找这棵树上某个元素的根节点，由于层 //数变低，相应的速度也会快很多
#endif |
UnionFindTestHelper.h：
|
#ifndef UNIONFINDTESTHELPER_H #define UNIONFINDTESTHELPER_H
#include"UnionFind.h" #include <iostream> #include <ctime> using namespace std;
namespace UnionFindTestHelper {
void testUF(int n) { //设置随机种子 srand(time(NULL)); UF::UnionFind uf = UF::UnionFind(n);
time_t startTime = clock();
//先进行n次的并，即 Union 操作 for (int i = 0; i < n; i++) { int a = rand() % n; int b = rand() % n; uf.unionElements(a, b); }
//再进行n次的查，即 Find 操作 for (int i = 0; i < n; i++) { int a = rand() % n; int b = rand() % n; uf.isConnected(a, b); }
time_t endTime = clock();
//打印2*n个操作耗费的时间 cout << "UF, " << 2 * n << " ops, " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl; } }
#endif |
main.cpp：
|
#include"UnionFindTestHelper.h" #include <iostream> using namespace std;
int main() { //规模是一百万 int n = 1000000;
UnionFindTestHelper::testUF(n);
system("pause"); return0; } |
运行一览：
程序 2：路径压缩的优化（在程序 1 的基础上，修改UnionFind.h 即可）
UnionFind.h：
|
#ifndef UNIONFIND_H #define UNIONFIND_H
#include <iostream> #include <cassert> using namespace std;
//并查集：Quick Union + rank + path compression namespace UF {
class UnionFind {
private: int* parent; int* rank; // rank[i]表示以i为根的集合所表示的树的层数 int count;
public: UnionFind(int count) { this->count = count; parent = newint[count]; rank = newint[count]; //在初始情况下，并查集里的元素，两两之间互不连接 for (int i = 0; i < count; i++) { parent[i] = i; rank[i] = 1; } }
~UnionFind() { delete []parent; delete []rank; }
int size() { return count; }
int find(int p) {
assert(p >= 0 && p < count);
//path compression 2 if (p != parent[p]) { //这个版本的路径压缩实际上用时更长 //虽然理论上更优（采用递归） parent[p] = find(parent[p]); }
//此时，parent[p]是整棵树的根节点 return parent[p]; }
bool isConnected(int p, int q) { return find(p) == find(q); }
void unionElements(int p, int q) {
int pRoot = find(p); int qRoot = find(q);
if (pRoot == qRoot) { return; }
//rank小的那棵树的根节点指向rank大的那棵树的根节点 if (rank[pRoot] < rank[qRoot]) { parent[pRoot] = qRoot; } else if (rank[qRoot] < rank[pRoot]) { parent[qRoot] = pRoot; } // rank[pRoot] == rank[qRoot] else { //可互换 parent[pRoot] = qRoot; rank[qRoot] ++; }
}
void show() { for (int i = 0; i < count; i++) { cout << i << " : " << parent[i] << endl; } } }; }
//路径压缩的最优的情况，能将整个路径压缩成 2 层，所有的节点 //都指向一个根 // //在这种情况下，搜索任何节点最多只要一步，就找到了根节点 // //但实际上用时更长一些，这个时间消耗主要是递归过程所产生的开销 // //不过，虽然递归过程产生了一些额外开销，但从逻辑上来讲，这样做 //是更优的，只是实践效果并不是特别的好 // //理论和实践通常会稍微有点出入，所以在实际的工作过程中也应该根据 //实际情况，灵活选择最合适的方式，而不一定是理论上最优的那个方式 // // // //此时，并查集的操作（Union和Find），时间复杂度近乎是O(1)的 // //注意：是近乎，不是完全。不难想象，经过路径压缩以后，在每次查找 //以后，每一位元素就离根节点非常近了，甚至在的这个优化版本的路径 //压缩，经过一次查询，查询路径上的所有节点，离根节点的距离，都变 //成 1 了。尽管如此，在这个过程中，依然有时间的消耗，并非每次操作 //都是 O(1) 级别的 // //对于这个时间的消耗，在数学上，数学家们发明了一个专门的函数来表达， //这个函数叫做 alpha
#endif |
运行一览：
【made by siwuxie095】