并查集为解决等价类问题提供了一个高效快速的数据结构,在许多涉及到等价类的算法中,他都扮演着
改进算法中使用的数据机构的角色,他对提高算法的效率是可见一斑,例如在带有限期的作业问题中,在求最小生成树Kruskal算法都可以使用并查集高效的实现.
const int DefaultSize = 20;
class UFSets{
public:
UFSets(int s = DefaultSize);
~UFSets();
void Union(int root1,int root2);
void WeightUnion(int root1,int root2);//基于加权规则的合并操作
//使合并树保持较小的深度
//减小Find的时间
int Find(int x);//查找x元素的集合,并返回集合的名
int CollapsingFind(int x);//查找的过程中基于折叠规则进行路径压缩
private:
int *parent;
int size;
};
UFSets::UFSets(int s){
size = s;
parents = new int[size+1];
for(int i= 0; i<= size; i++)
parent[i] = -1;
}
int UFSets::Find(int x){
if(parent[x] < 0)
return x;
else
return Find(parent[x]);
}
void UFSets::Union(int root1,int root2){
parent[root2] = root1;
}
void UFSets::WeightUnion(int root1,int root2){
int weight = parent[root1] + parent[root2];
if(parent[root1] < parent[root2]){
parent[root1] = root2;
parent[root2] = temp;
}
else{
parent[root2] = root1;
parent[root1] = temp;
}
}
int UFSets::CollapsingFind(int x){
int temp;
for(int j = x; parent[j] >= 0; j = parent[j]);//查找x的根
while(x != j){//把x所在的一支的节点依次连到根节点,使得树的深度
temp = parent[x];//保持很小
parent[x] = j;
x = temp;
}
}
分享到:
相关推荐
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
并查集.并查集(Union-Find)是一种特殊的数据结构,它可以高效地管理一系列不交集的合并和查询操作。这种数据结构通常用树形结构来表示,并且常常在实际应用中以森林的形式存在。
并查集基础 acm 算法 poj oi 并查集基础.ppt
基于Union-Find数据结构实现Kruskal求最小生成树,代码设计及变量命名附详细注释。基于Union-Find数据结构实现Kruskal求最小生成树,代码设计及变量命名附详细注释。
利用数据结构中的并查集结构,根据输入的迷宫的行数和列数,自动生成迷宫。
数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 ...
本文件含有并查集的实现,其中 find 和 union 均采用了路径压缩。
并查集的最坏情况分析,TARJAN的经典论文。ACM/OI选手可进行下载学习
这是 Node.js 中 union-find 数据结构的一个实现。 在做个人项目时,我没有找到适合我需求的 NPM 模块并创建了它。 如果有人对此模块感兴趣,或者想要添加功能,请随时与我联系。 谢谢。 安装 $ npm install node-...
Disjoint-Sets-using-Union-Find:使用联合查找和树进行路径压缩的不相交集
UnionFind.h
UnionFind-2x2
Union-Find: A Data Structure for Disjoint Set Operations