赞
踩
并查集是一种树型的数据结构,它可以高效地进行如下操作:
特点:
public class UF {
//记录结点元素和该元素所在分组的标识
private int[] eleAndGroup;
//记录并查集中数据的分组个数
private int count;
//初始化并查集
public UF(int N){
//初始化分组的数量,默认情况下,有N个分组
this.count = N;
//初始化eleAndGroup数组
this.eleAndGroup = new int[N];
//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素,并且让每个索引处的值(该元素所在的组的标识符)等于该索引
for (int i = 0; i < eleAndGroup.length; i++) {
eleAndGroup[i] = i;
}
}
//获取当前并查集中的数据有多少个分组
public int count(){
return count;
}
//元素p所在分组的标识符
public int find(int p){
return eleAndGroup[p];
}
//判断并查集中元素p和元素q是否在同一分组中
public boolean connected(int p,int q){
return find(p) == find(q);
}
//把p元素所在分组和q元素所在分组合并
public void union(int p,int q){
//判断元素q和p是否已经在同一分组中,如果已经在同一分组中,结束方法
if (connected(p,q)){
return;
}
//找到p所在分组的标识符
int pGroup = find(p);
//找到q所在分组的标识符
int qGroup = find(q);
//合并分组:让p所在组的所有元素的组标识符变为q所在分组的标识符
for (int i = 0; i < eleAndGroup.length; i++) {
if (eleAndGroup[i]==pGroup){
eleAndGroup[i] = qGroup;
}
}
//分组个数-1
this.count--;
}
}
public class Test {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("请录入并查集中元素的个数:");
int N = sc.nextInt();
UF uf = new UF(N);
while(true) {
System.out.println("请录入要合并的第一个点:");
int p = sc.nextInt();
System.out.println("请录入要合并的第二个点:");
int q = sc.nextInt();
// 判断p和q是否在同一分组
if (uf.connected(p,q)) {
System.out.println("结点" + p + "结点" + q + "已经在同一分组");
continue;
}
uf.union(p, q);
System.out.println("总共还有" + uf.count() + "个分组");
}
}
}
请录入并查集中元素的个数:
5
请录入要合并的第一个点:
1
请录入要合并的第二个点:
3
总共还有4个分组
请录入要合并的第一个点:
1
请录入要合并的第二个点:
3
结点1结点3已经在同一分组
请录入要合并的第一个点:
如果将并查集中存储的每个整数表示一台网络中的计算机,就可以通过connected(int p, int q)来检测网络中的两台计算机是否连通,也可以通过union(int p, int q)使p和q连通,以便通信。
如果让每个数据都连通,至少要调用N-1次union方法,而在union方法中使用了for循环,因此时间复杂度是O(N^2),如果要解决大规模问题,不太合适,需要优化。
对eleAndGroup数组的含义重新设定:
public class UF_Tree {
//记录结点元素和该元素所在分组的标识
private int[] eleAndGroup;
//记录并查集中数据的分组个数
private int count;
//初始化并查集
public UF_Tree(int N){
//初始化分组的数量,默认情况下,有N个分组
this.count = N;
//初始化eleAndGroup数组
this.eleAndGroup = new int[N];
//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素,并且让每个索引处的值(该元素所在的组的标识符)等于该索引
for (int i = 0; i < eleAndGroup.length; i++) {
eleAndGroup[i] = i;
}
}
//获取当前并查集中的数据有多少个分组
public int count(){
return count;
}
//判断并查集中元素p和元素q是否在同一分组中
public boolean connected(int p,int q){
return find(p) == find(q);
}
//元素p所在分组的标识符
public int find(int p){
while(true){
if (p == eleAndGroup[p]){
return p;
}
p = eleAndGroup[p];
}
}
//把p元素所在分组和q元素所在分组合并
public void union(int p,int q){
//找到p元素和q元素所在组对应的树的根结点
int pRoot = find(p);
int qRoot = find(q);
//如果p和q已经在同一分组,则不需要合并了
if (pRoot==qRoot){
return;
}
//让p所在的树的根结点的父结点为q所在树的根结点即可
eleAndGroup[pRoot] = qRoot;
//分组数量-1
this.count--;
}
}
如果让每个数据都连通,要调用N-1次union方法,但是union调用了find算法,UF的find时间复杂度为O(1),现在UF_Tree的find平均时间复杂度为O(N/2),因此连通所有的时间复杂度是O(N^2/2),比之前好,但依然有优化空间。
为了能保证每次合并时,都能把小树合并到大树上,我们新增一个数组来记录每个根结点对应的树中元素的个数。
public class UF_Tree_Weighted {
//记录结点元素和该元素所在分组的标识
private int[] eleAndGroup;
//记录并查集中数据的分组个数
private int count;
//用来存储每一个根结点对应的树中保存的结点个数
private int[] sz;
//初始化并查集
public UF_Tree_Weighted(int N){
//默认情况下,有N个分组
this.count = N;
//初始化eleAndGroup数组
this.eleAndGroup = new int[N];
//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素,并且让每个索引处的值(该元素所在的组的标识符)等于该索引
for (int i = 0; i < eleAndGroup.length; i++) {
eleAndGroup[i] = i;
}
this.sz = new int[N];
//默认情况下,sz中每个索引处的值都是1
for (int i = 0; i < sz.length; i++) {
sz[i] = 1;
}
}
//获取当前并查集中的数据有多少个分组
public int count(){
return count;
}
//判断并查集中元素p和元素q是否在同一分组中
public boolean connected(int p,int q){
return find(p) == find(q);
}
//元素p所在分组的标识符
public int find(int p){
while(true){
if (p == eleAndGroup[p]){
return p;
}
p = eleAndGroup[p];
}
}
//把p元素所在分组和q元素所在分组合并
public void union(int p,int q){
//找到p元素和q元素所在组对应的树的根结点
int pRoot = find(p);
int qRoot = find(q);
//如果p和q已经在同一分组,则不需要合并了
if (pRoot==qRoot){
return;
}
//判断proot对应的树大还是qroot对应的树大,最终需要把较小的树合并到较大的树中
if (sz[pRoot] < sz[qRoot]){
eleAndGroup[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
}else{
eleAndGroup[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
//分组数量-1
this.count--;
}
}
有文件traffic_project.txt,下面是文件内容及数据解释:
public class Traffic_Project {
public static void main(String[] args) throws IOException {
// 创建输入流
BufferedReader reader = new BufferedReader(new FileReader("src/traffic_project.txt"));
// 读取城市数目,初始化并查集
int number = Integer.parseInt(reader.readLine());
UF_Tree_Weighted uf = new UF_Tree_Weighted(number);
// 读取已经修建好的道路数目
int roadNumber = Integer.parseInt(reader.readLine());
// 循环读取已经修建好的道路,并调用union方法
for (int i=0; i<roadNumber; i++) {
String line = reader.readLine();
int p = Integer.parseInt(line.split(" ")[0]);
int q = Integer.parseInt(line.split(" ")[1]);
uf.union(p, q);
}
// 获取剩余的分组数量
int groupNumber = uf.count();
// 计算出还需要修建的道路
System.out.println("还需要修建" + (groupNumber-1) + "条道路,城市才能相通");
}
}
还需要修建12条道路,城市才能相通
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。