并查集数据结构总结
1、在「并查集」数据结构中，其中心思想是将所有连接的顶点，无论是直接连接还是间接连接，都将他们指向同一个父节点或者根节点。此时，如果要判断两个顶点是否具有连通性，只要判断它们的根节点是否为同一个节点即可。
在「并查集」数据结构中，它的两个灵魂函数，分别是 find和 union。find 函数是为了找出给定顶点的根节点。 union 函数是通过更改顶点根节点的方式，将两个原本不相连接的顶点表示为两个连接的顶点。对于「并查集」来说，它还有一个重要的功能性函数 connected。它最主要的作用就是检查两个顶点的「连通性」。find 和 union 函数是「并查集」中必不可少的函数。connected 函数则需要根据题目的意思来决定是否需要。
2、并查集类型：
- QuickFind并查集
核心：root数组存放每个结点的根结点 - QuickUnion并查集
核心：root数组存放每个结点的父结点 - 按秩合并的并查集
核心：针对quickunion中的union函数的改进，通过树的高度选取父结点 - 路径压缩优化的并查集
核心： 针对quickunion中的find函数的改进，利用递归思想在find()时将每个结点的父结点改为根结点
3、代码 - quick find:
#include
#include
using namespace std;
class quick_find{
private:
vector root;
int size;
public:
quick_find(int size){
this->size = size;
for(int i=0;isize;i++){
root.push_back(i);
}
}
int _find(int ID){
return root[ID];
}
void _union(int x,int y){
int rootX = _find(x);
int rootY = _find(y);
if(rootX!=rootY){
for(int i=0;isize;i++){
if(root[i]==rootY){
root[i] = rootX;
}
}
}
}
void _display(){
cout<<"root: "<size;i++){
cout< - quick union
#include
#include
using namespace std;
class quick_union{
private:
vector root;
int size;
public:
quick_union(int size){
this->size = size;
for(int i=0;isize;i++){
root.push_back(i);
}
}
int _find(int ID){
if(ID == root[ID]) return ID;
//else return _find(root[ID]);
else return root[ID]=_find(root[ID]);//path compression
}
void _union(int x,int y){
int rootX = _find(x);
int rootY = _find(y);
if(rootX!=rootY){
root[rootY] = rootX;
}
}
void _display(){
cout<<"root: "<size;i++){
cout< root;
vector rank;
int size;
public:
quick_union_sorted_by_rank(int size){
this->size = size;
for(int i=0;isize;i++){
root.push_back(i);
rank.push_back(1);
}
}
int _find(int ID){
if(ID == root[ID]) return ID;
//else return _find(root[ID]);
else return root[ID]=_find(root[ID]);//path compression
}
void _union(int x,int y){
int rootX = _find(x);
int rootY = _find(y);
if(rootX!=rootY){
if(rank[rootX]>rank[rootY]){
root[rootY] = rootX;
}
else if(rank[rootX]size;i++){
cout<size;i++){
cout<