首页 > 代码库 > 不相交集类(并查集）
不相交集类(并查集）
并查集 就是只有合并和 查找操作的一种数据结构 很简单，主要判断一个元素是否在一个集合里 主要应用在最小生成树（Kruskal算法)，看到图的时候会将实现代码贴上
package chapter8;
/**
* 类名：DisjSets 说明：实现并查集 按高度求并，路径压缩 s[i]代表i的父节点
*/
public class DisjSets {
public DisjSets(int numElements) {
s = new int[numElements];
for (int i = 0; i < numElements; i++)
s[i] = -1;
}
/**
* 方法名：union1 说明：将root2的父节点指为root1
*/
public void union1(int root1, int root2) {
s[root1] = root2;
}
/**
* 方法名：union2 说明：按高度求并
*/
public void union2(int root1, int root2) {
root1 = find(root1);
root2 = find(root2);
if(root1 == root2)
return;
else{
//root1的高度大于 root2的 则将root2成为root1的子树
if(s[root1] > s[root2])
s[root2] = root1;
else{
if(s[root1] == s[root2])
s[root2]++;
s[root1] = root2;
}
}
}
/**
* 方法名：union3 说明：按树的大小来合并，每个根的数组元素就是它包含树的大小的负值
*/
public void union3(int root1, int root2) {
root1 = find(root1);
root2 = find(root2);
if (root1 == root2)
return;
else {
// s[root1]< s[root2]说明 root1树大 将root2成为它的子树
if (s[root1] < s[root2]) {
s[root2] = root1;
s[root1] += s[root2];//更新根节点
} else
s[root1] = root2;
s[root2] += s[root1] + s[root2];
}
}
/**
* 方法名：find 说明：实现路径压缩 只是加了简单的一步 将s[x]指向不断递归所得到的根
*/
public int find(int x) {
if (s[x] < 0)
return x;
else
return s[x] = find(s[x]);
}
private int[] s;
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
不相交集类(并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。