算法与数据结构（六）并查集
2017-09-17 本文已影响81人
天涯明月笙
并查集 Union Find
- 图相关算法的实现。
- 一种不一样的树形结构
连接问题 Connectivity Problem
可视化的来看连接问题：
连接问题
左上右下是否是连接的呢？
意义：实际应用中的作用
-
网络中节点间的连接状态
- 网络是个抽象的概念：用户之间形成的网络
-
社交网络：Facebook中用户a和b中的联系（好友关系）。是否能联系到。
-
音乐电影书籍，多媒体之间形成网络。
-
互联网网页之间形成的网络
-
路由器和路由器之间形成的也是网络
-
道理交通，航班调度都是网络
数学中的集合类实现
并就是实现并集。& 查询
连接问题 & 路径问题
比路径问题要回答的问题少（路径是什么，连接问题只问有没有连）
- 和二分查找作比较：顺序查找法顺便回答了rank。和前面其他元素的位置
- 和select作比较：排好序回答问题更多。快排思路select回答问题更少
- 和堆作比较：只关心最大最小。
除了回答问题本身之外是不是额外的回答了别的问题。很有可能就存在
更高效的算法。：因为高效算法不需要回答额外的问题。
实现一个最简单的并查集 Union Find
对于一组数据，主要支持两个动作：
- union( p , q )
- find( p )
用来回答一个问题
- isConnected( p , q )
最简单的表示方式；
数组。0,1.
0-4 5-9
0-4是一组，5-9是一组。组内之间有联系
奇偶
奇数是一组，偶数是一组。
namespace UF1 {
class UnionFind {
private:
int *id;
int count;
public:
UnionFind(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
}
~UnionFind() {
delete[] id;
}
//传入元素p，返回元素对应的id。
int find(int p) {
assert(p >= 0 && p < count);
return id[p];
}
bool isConnected(int p, int q) {
return find(p) == find(q);
}
//传入两个元素，并
void unionElements(int p, int q) {
//找到两个元素的id
int pID = find(p);
int qID = find(q);
//比较id
if (pID == qID)
return;
for (int i = 0; i < count; i++)
//从头到尾的扫描时间复杂度O(n)
if (id[i] == pID)
id[i] = qID;
}
};
}
Testhelper.h:
namespace UnionFindTestHelper{
//n是数据量
void testUF1( int n ){
srand( time(NULL) );
UF1::UnionFind uf = UF1::UnionFind(n);
time_t startTime = clock();
for( int i = 0 ; i < n ; i ++ ){
int a = rand()%n;
int b = rand()%n;
uf.unionElements(a,b);
//O(n）
}
for(int i = 0 ; i < n ; i ++ ){
int a = rand()%n;
int b = rand()%n;
uf.isConnected(a,b);
//时间复杂度只有O(1)
}
time_t endTime = clock();
cout<<"UF1, "<<2*n<<" ops, "<<double(endTime-startTime)/CLOCKS_PER_SEC<<" s"<<endl;
}
}
main.cpp:
int main() {
int n = 100000;
UnionFindTestHelper::testUF1(n);
return 0;
}
运行结果：
快速查找，并很慢
quick find 查找时只需要O(1)级别。但是并确很慢
并查集的另一种实现思路
常规实现思路
将每一个元素，看做是一个节点。
元素节点
每个元素拥有一个指向父节点的指针。然后最上面的父节点指针指向自己。
Quick Union
数组存放父亲
parent(i) = i;
初始状态
union 3 4
union 3 4
union 3 8
union 3 8
union 6 5
union 6 5
union 9 4
union 9 4
要将9连接到4的根节点8上去。数组中：4-3-8-8 8是4的根节点。9指向8.
4和9连接在一起：因为根相同。
成果
其中6和2连接是6的根0和2的根1选取了1将0挂上。
namespace UF2{
class UnionFind{
private:
int* parent;
int count;
public:
UnionFind(int count){
parent = new int[count];
this->count = count;
for( int i = 0 ; i < count ; i ++ )
parent[i] = i;
}
~UnionFind(){
delete[] parent;
}
//不断向上找父亲
int find(int p){
assert( p >= 0 && p < count );
while( p != parent[p] )
p = parent[p];
return p;
}
//看是否能找到同样的根
bool isConnected( int p , int q ){
return find(p) == find(q);
}
//找到p的根，和q的根
void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
//把根挂到另一个的根
parent[pRoot] = qRoot;
}
};
}
运行结果：
运行结果
当n大的时候，方法1更优了。
并查集的优化
问题：
union 9,4 & union 4 9
union 9 4
9的元素少，将它指向4的根节点。形成的树层数低。
// 我们的第三版Union-Find
namespace UF3{
class UnionFind{
private:
int* parent; // parent[i]表示第i个元素所指向的父节点
int* sz; // sz[i]表示以i为根的集合中元素个数
int count; // 数据个数
public:
// 构造函数
UnionFind(int count){
parent = new int[count];
sz = new int[count];
this->count = count;
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
sz[i] = 1;
}
}
// 析构函数
~UnionFind(){
delete[] parent;
delete[] sz;
}
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
int find(int p){
assert( p >= 0 && p < count );
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
}
// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
bool isConnected( int p , int q ){
return find(p) == find(q);
}
// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
// 根据两个元素所在树的元素个数不同判断合并方向
// 将元素个数少的集合合并到元素个数多的集合上
if( sz[pRoot] < sz[qRoot] ){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}
else{
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}
};
}
运行结果：
运行结果
优化相当明显。
int main() {
// 使用10000的数据规模
int n = 100000;
// 虽然isConnected只需要O(1)的时间, 但由于union操作需要O(n)的时间
// 总体测试过程的算法复杂度是O(n^2)的
UnionFindTestHelper::testUF1(n);
// 对于UF2来说, 其时间性能是O(n*h)的, h为并查集表达的树的最大高度
// 这里严格来讲, h和logn没有关系, 不过大家可以简单这么理解
// 我们后续内容会对h进行优化, 总体而言, 这个h是远小于n的
// 所以我们实现的UF2测试结果远远好于UF1, n越大越明显:)
UnionFindTestHelper::testUF2(n);
// 对于UF3来说, 其时间性能依然是O(n*h)的, h为并查集表达的树的最大高度
// 但由于UF3能更高概率的保证树的平衡, 所以性能更优
UnionFindTestHelper::testUF3(n);
return 0;
}
100万在1秒之内
union 4 2
合并4和2
依靠集合的size来决定谁指向谁并不完全合理。根据层数才最合理
基于rank的优化
- rank[i] 表示根节点为i的树的高度
namespace UF4{
class UnionFind{
private:
int* rank; // rank[i]表示以i为根的集合所表示的树的层数
int* parent; // parent[i]表示第i个元素所指向的父节点
int count; // 数据个数
public:
// 构造函数
UnionFind(int count){
parent = new int[count];
rank = new int[count];
this->count = count;
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
// 析构函数
~UnionFind(){
delete[] parent;
delete[] rank;
}
// 查找过程, 查找元素p所对应的集合编号
// O(h)复杂度, h为树的高度
int find(int p){
assert( p >= 0 && p < count );
// 不断去查询自己的父亲节点, 直到到达根节点
// 根节点的特点: parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
}
// 查看元素p和元素q是否所属一个集合
// O(h)复杂度, h为树的高度
bool isConnected( int p , int q ){
return find(p) == find(q);
}
// 合并元素p和元素q所属的集合
// O(h)复杂度, h为树的高度
void unionElements(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[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
}
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // 此时, 我维护rank的值
}
}
};
}
// 对于UF3来说, 其时间性能依然是O(n*h)的, h为并查集表达的树的最大高度
// 但由于UF3能更高概率的保证树的平衡, 所以性能更优
UnionFindTestHelper::testUF3(n);
// UF4虽然相对UF3进行有了优化, 但优化的地方出现的情况较少,
// 所以性能更优表现的不明显, 甚至在一些数据下性能会更差
UnionFindTestHelper::testUF4(n);
运行结果
路径压缩（path Compression）
前面我们都在优化union。其实Find我们也可以进行优化。
1
我们要find4
4去连接它爷爷
4去连接它爷爷。下面考查2.
2连接爷爷
路径压缩
int find(int p){
assert( p >= 0 && p < count );
// path compression 1
while( p != parent[p] ){
parent[p] = parent[parent[p]];
p = parent[p];
}
}
最优的情况
写一个递归的函数：调用findx，返回的就是x节点的根。让每个parentx指向findx的结果。findx的结果也是Findparentx的结果。找x的时候，将x的Findparent的结果，指向父亲的结果。
代码：
// path compression 2, 递归算法
if( p != parent[p] )
parent[p] = find( parent[p] );
return parent[p];
优化情况并不明显。甚至因为递归的消耗，。所以理论最优不一定实际好。
并查集的操作，时间复杂度近乎是O(1)的。
- 经过路径压缩：近乎1就能到根节点。
解决图，网络连接。最短路径。路径是什么？都得使用图论。
