并查集
本篇博客参照了如下博客内容： http://www.cnblogs.com/horizonice/p/3658176.html
并查集
并查集是一种树形结构，又叫“不相交集合”，保持了一组不相交的动态集合，每个集合通过一个代表来识别，代表即集合中的某个成员，通常选择根做这个代表。
初始化
用数组来建立一个并查集，数组下标代表元素，下标对应的值代表父节点，全部初始化为-1，根节点为一个集合的元素个数，数组的长度为并查集的初始连通分量的个数。并查集要求各集合是不相交的，因此要求x没有在其他集合中出现过。算法如下：
//构造函数
UF(int size){
this->count = size;
array = new int[size];
for(int i = 0 ; i < size ; i++){
this->array[i] = -1;
}
}查找操作
返回能代表x所在集合的节点，通常返回x所在集合的根节点。这里的查找操作通常采用路径压缩的办法，即在查找过程中组不减小树的高度，把元素逐步指向一开始的根节点。这样下次再找根节点的时间复杂度会变成o(1)。如下图所示
这里写图片描述
算法如下：
//查找操作，路径压缩
int Find(int x){
if(this->array[x] < 0){
return x;
}else{
//首先查找x的父节点array[x]，然后把根变成array[x],之后再返回根
return this->array[x] = Find(this->array[x]);
}
}并操作
将包含x,y的动态集合合并为一个新的集合。合并两个集合的关键是找到两个集合的根节点，如果两个根节点相同则不用合并；如果不同，则需要合并。 这里对并操作有两种优化：根节点存树高的相反数或者根节点存集合的个数的相反数，这两种方法统称按秩归并。通常选用第二种方法。 归并过程如下图：
这里写图片描述
算法如下：
//并操作,跟结点存储集合元素个数的负数
//通过对根结点的比较
void Uion(int root1, int root2){
root1 = this->Find(root1);
root2 = this->Find(root2);
if(root1 == root2){
return;
}else if(this->array[root1] < this->array[root2]){
//root1所代表的集合的个数大于root2所代表集合的个数
//因为为存放的是元素个数的负数
this->array[root1] += this->array[root2];
this->array[root2] = root1;
count--;
}else{
this->array[root2] += this->array[root1];
this->array[root1] = root2;
count--;
}
}
}全部代码如下：
#include <iostream>
#include <string.h>
using namespace std;
class UF{
private:
int* array;
//并查集中的联通分量的个数,初始化为数组大小
int count;
public:
//构造函数
UF(int size){
this->count = size;
array = new int[size];
for(int i = 0 ; i < size ; i++){
this->array[i] = -1;
}
}
//查找操作，路径压缩
int Find(int x){
if(this->array[x] < 0){
return x;
}else{
//首先查找x的父节点array[x]，然后把根节点变成array[x],之后再返回根
return this->array[x] = Find(this->array[x]);
}
}
//并操作,跟结点存储集合元素个数的负数
//通过对根结点的比较
void Uion(int root1, int root2){
root1 = this->Find(root1);
root2 = this->Find(root2);
if(root1 == root2){
return;
}else if(this->array[root1] < this->array[root2]){
//root1所代表的集合的个数大于root2所代表集合的个数
//因为为存放的是元素个数的负数
this->array[root1] += this->array[root2];
this->array[root2] = root1;
count--;
}else{
this->array[root2] += this->array[root1];
this->array[root1] = root2;
count--;
}
}
//判断两个集合是否属于一个集合
bool check(int root1,int root2){
root1 = this->Find(root1);
root2 = this->Find(root2);
return root1 == root2;
}
//放回连通分量个数
int getCount(){
return this->count;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录