扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
创新互联www.cdcxhl.cn八线动态BGP香港云服务器提供商，新人活动买多久送多久，划算不套路！
这篇文章主要介绍Java实现快速并查集的方法，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！
在一些应用的问题中，需将n个不同的元素划分成一组不相交的集合。开始时，每个元素自成一格单元素集合，然后按一定顺序将属于同一组的元素的集合合并。其间要反复用到查询某个元素属于哪个集合的运算。适合于描述这类问题的抽象数据类型称为并查集。
1. 并查集的概述
并查集的数学模型是一组不相交的动态集合的集合S={A,B,C,...}，它支持以下的运算：
(1)union(A,B)：将集合A和B合并，其结果取名为A或B；
(2)find(x)：找出包含元素x的集合，并返回该集合的名字。
在并查集中需要两个类型的参数：集合名字的类型和元素的类型。在许多情况下，可以用整数作为集合的名字。如果集合中共有n个元素，可以用范围【1：n】以内的整数表示元素。实现并查集的一个简单方法是使用数组表示元素及其所属子集的关系。其中，用数组下标表示元素，用数组单元记录该元素所属的子集名字。如果元素类型不是整型，则可以先构造一个映射，将每个元素映射成一个整数。这种映射可以用散列表或其他方式实现。
2. 并查集的实现
采用数结构实现并查集的基本思想是，每个集合用一棵树表示。树的结点用于存储集合中的元素名。每个树结点还存放一个指向其父结点的指针。数根结点处的元素代表该数所表示的集合。利用映射可以找到集合中所对应的数结点。
父亲数组是实现上述数结构的有效方法。
Java实现代码：
public class UnionFind {
Node[] node; //父亲数组
//并查集中的结点
private static class Node{
int parent;
boolean root;
private Node(){
parent = 1;
root = true;
}
}
//将每个元素初始化为一颗单结点树
public UnionFind(int n){
node = new Node[n + 1];
for(int e= 0; e <= n; e++){
node[e] = new Node();
}
}
} 
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网