java算法实例_合并元素&&判断元素是否连通
案例1:简单的实现方式，直接遍历
代码：
package me.ele.union_find;
import java.util.Arrays;
import java.util.List;
/**
* 快速查找 UC（union find）
* <p>
* 有一些元素 a b c d e f g h ......
*
* @author LZJ
* @create 2018-10-03 13:40
**/
public class QuickFindUF {
private int[] idArr;
/**
* 初始化 数组，数组中每个位置上元素的值 即 元素的下标
*
* @param n
*/
public QuickFindUF(int n) {
idArr = new int[n];
for (int i = 0; i < n; i++) {
idArr[i] = i;
}
}
/**
* 给定两个元素，查询两个元素是否在统一集合内
*
* @param p
* @param q
* @return 如果两个元素在数组中的值 相等，即代表两个元素连通
*/
public boolean find(int p, int q) {
return idArr[p] == idArr[q];
}
/**
* 合并两个元素 即 将两个元素连通
* 每次合并 两个元素的时候，遍历当前数组，将其中所有符合（值与p元素的值相等的）所有元素 替换为q的值
* 这样，p元素以及之前的符合条件的元素 都会与q元素合并（连通）
*
* @param p
* @param q
*/
public void union(int p, int q) {
int length = idArr.length;
for (int i = 0; i < length; i++) {
if (idArr[i] == idArr[p]) {
idArr[i] = idArr[q];
}
}
}
}测试：
public static void main(String[] args) {
// [0-9]十个元素放置到数组 idArr 之所以使用0-9不重复的数字 是因为想要唯一区分每个元素
QuickFindUF quickFindUF = new QuickFindUF(10);
System.out.println("------- 合并（连通）元素：1和2 -------");
quickFindUF.union(1, 2);
System.out.println("合并后å数组id：" + Arrays.toString(quickFindUF.idArr));
System.out.println("------- 合并（连通）元素：2和3 -------");
quickFindUF.union(2, 3);
System.out.println("数组id：" + Arrays.toString(quickFindUF.idArr));
System.out.println("------- 合并（连通）元素：4和5 -------");
quickFindUF.union(4, 5);
System.out.println("数组id：" + Arrays.toString(quickFindUF.idArr));
System.out.println("========");
System.out.println("元素：1和2是否连通-->" + quickFindUF.find(1, 2));
System.out.println("元素：1和4是否连通-->" + quickFindUF.find(1, 4));
System.out.println("元素：4和5是否连通-->" + quickFindUF.find(4, 5));
}运行结果：
案例2:通过 根的方式区分元素是否在同一集合
代码：
package me.ele.union_find;
import java.util.Arrays;
/**
* 上一个 QuickFindUF算法 合并元素的时候，将所有元素的直接连在一起
* 在本QuickUnionUF中，将会区分root节点 root节点一致的两个元素是连通的
*
* @author LZJ
* @create 2018-10-03 14:29
**/
public class QuickUnionUF {
private int[] idArr;
public QuickUnionUF(int n) {
idArr = new int[n];
for (int i = 0; i < n; i++) {
idArr[i] = i;
}
}
public int root(int p) {
while (idArr[p] != p) {
p = idArr[p];
}
return p;
}
public void union(int p, int q) {
int root_p = root(p);
int root_q = root(q);
idArr[root_p] = root_q;
}
public boolean find(int p, int q) {
return root(p) == root(q);
}
}
测试：
public static void main(String[] args) {
QuickUnionUF quickUnionUF = new QuickUnionUF(10);
System.out.println(Arrays.toString(quickUnionUF.idArr));
System.out.println("------- 合并1 和 2：-------");
quickUnionUF.union(1, 2);
System.out.println(Arrays.toString(quickUnionUF.idArr));
System.out.println("判断 1 和2 是否连通：");
System.out.println(quickUnionUF.find(1, 2));
System.out.println("------- 合并2 和 4：-------");
quickUnionUF.union(2, 4);
System.out.println(Arrays.toString(quickUnionUF.idArr));
System.out.println("判断 2 和4 是否连通：");
System.out.println(quickUnionUF.find(2, 4));
System.out.println("1 的根：" + quickUnionUF.root(1));
System.out.println("判断 1 和4 是否连通：");
System.out.println(quickUnionUF.find(1, 4));
}运行结果：
案例3: 在案例2的基础上添加权重
代码：
package me.ele.union_find;
import java.util.Arrays;
/**
* 有root并且 带权重的 合并
* @author LZJ
* @create 2018-10-03 14:46
**/
public class WeightUnionUF {
int[] idArr;
int[] weight;
public WeightUnionUF(int n) {
idArr = new int[n];
weight = new int[n];
for (int i = 0; i < n; i++) {
idArr[i] = i;
weight[i] = 1;
}
}
private int root(int p) {
while (idArr[p] != p) {
idArr[p] = idArr[idArr[p]];
p = idArr[p];
}
return p;
}
public void union(int p, int q) {
int root_p = root(p);
int root_q = root(q);
if (weight[root_q] >= weight[root_p]) {
idArr[root_p] = root_q;
weight[root_q] += weight[root_p];
weight[root_p] = 0;
} else {
idArr[root_q] = root_p;
weight[root_p] += weight[root_q];
weight[root_q] = 0;
}
}
public boolean find(int p, int q) {
return root(p) == root(q);
}
}
测试：
public static void main(String[] args) {
WeightUnionUF weightUnionUF = new WeightUnionUF(10);
System.out.println("idArr:"+ Arrays.toString(weightUnionUF.idArr));
System.out.println("weight:"+ Arrays.toString(weightUnionUF.weight));
System.out.println("-----合并 1 和 3-----");
weightUnionUF.union(1,3);
System.out.println("idArr:"+ Arrays.toString(weightUnionUF.idArr));
System.out.println("weight:"+ Arrays.toString(weightUnionUF.weight));
System.out.println("1 和 3是否连通："+weightUnionUF.find(1,3));
System.out.println("-----合并 1 和 4-----");
weightUnionUF.union(1,4);
System.out.println("idArr:"+ Arrays.toString(weightUnionUF.idArr));
System.out.println("weight:"+ Arrays.toString(weightUnionUF.weight));
System.out.println("1 和 3是否连通："+weightUnionUF.find(1,3));
System.out.println("1 和 4是否连通："+weightUnionUF.find(1,4));
System.out.println("3 和 4是否连通："+weightUnionUF.find(3,4));
System.out.println("-----合并 3 和 4-----");
weightUnionUF.union(3,4);
System.out.println("idArr:"+ Arrays.toString(weightUnionUF.idArr));
System.out.println("weight:"+ Arrays.toString(weightUnionUF.weight));
System.out.println("1 和 3是否连通："+weightUnionUF.find(1,3));
System.out.println("1 和 4是否连通："+weightUnionUF.find(1,4));
System.out.println("3 和 4是否连通："+weightUnionUF.find(3,4));
}运行结果：