作者:whisper
链接:http://proprogrammar.com:443/article/383-4
声明:请尊重原作者的劳动,如需转载请注明出处
本人抱着学习的目的写这篇文章,本人算法水平有限,在接触了相关概念,并动手操作过,看了相关的资料以后,对所学习内容做一个记录,其实主要就是拼凑看过的文章中的内容,起一个备忘的作用,如有错误,不全,幼稚的地方,还请见谅。
并查集是一种数据结构, 常用于描述集合,经常用于解决此类问题:某个元素是否属于某个集合,或者某个元素和另一个元素是否同属于一个集合
即有一些元素,把这些元素分组,组内元素是相互关联的,形成一棵树形结构,不同的组在一起形成森林
有两个概念:
weight:即一个分组中元素的数量
height:即一个分组形成的树的高度
有两个操作:
find:找一个元素所在分组的根元素
注:find操作中还可以进行路径压缩
union:合并两个元素所在的分组为一个分组
附加操作:
计算分组的数量
判断两个元素是否位于同一分组
下面看一下具体的算法,重点代码有相应注释
public class UnionFind
{
private int[] parent;
private int size;
// 设定并查集大小并初始化
public UnionFind(int size) {
this.size = size;
parent = new int[size];
for (int i = 0; i < size; i++) {
// 每个元素都指向自己,即自己和自己一组
parent[i] = i;
}
}
// 查找分组的根结点
public int find(int element) {
while (element != parent[element]) {
element = parent[element];
}
return element;
}
// 判断是否属于同一分组,如果根相同即属于同一分组
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
// 合并两个元素的分组
public void unionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
if (firstRoot == secondRoot) {
return;
}
// 分组不同,将其中一个分组的根作为另一个分组的根
parent[firstRoot] = secondRoot;
}
/**
* 本并查集使用数组实现,为了更直观地看清内部数据,采用打印数组
*/
private void printArr() {
for (int parent : this.parent) {
System.out.print(parent + "\t");
}
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind union = new UnionFind(n);
System.out.println("初始:");
union.printArr();
System.out.println("连接了5 6");
union.unionElements(5, 6);
union.printArr();
System.out.println("连接了1 2");
union.unionElements(1, 2);
union.printArr();
System.out.println("连接了2 3");
union.unionElements(2, 3);
union.printArr();
System.out.println("连接了1 4");
union.unionElements(1, 4);
union.printArr();
System.out.println("连接了1 5");
union.unionElements(1, 5);
union.printArr();
System.out.println("1 6 是否连接:" + union.isConnected(1, 6));
System.out.println("1 8 是否连接:" + union.isConnected(1, 8));
}
上面是基本的算法,在进行两个分组合并的时候没有做特殊处理,可以进行两种处理,把weight小的分组的根节点连接到weight大的分组的根结点上,或者把height小的分组的根结点连接到height大的分组的根结点上,下面来看一下这两种情况
使用weight的情况
public class UnionFind {
private int[] parent;
private int[] weight;
private int size;
public UnionFind(int size) {
this.parent = new int[size];
this.weight = new int[size];
this.size = size;
// 在初始化分组的同时也初始化weight
for (int i = 0; i < size; i++) {
this.parent[i] = i;
this.weight[i] = 1;
}
}
public int find(int element) {
while (element != parent[element]) {
element = parent[element];
}
return element;
}
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public void unionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
// 如果已经属于同一个集合了,就不用再合并了。
if (firstRoot == secondRoot) {
return;
}
// 将weight小的分组连接到weight大的分组上
if (weight[firstRoot] > weight[secondRoot]) {
parent[secondRoot] = firstRoot;
weight[firstRoot] += weight[secondRoot];
} else {//weight[firstRoot] <= weight[secondRoot]
parent[firstRoot] = secondRoot;
weight[secondRoot] += weight[firstRoot];
}
}
private void printArr(int[] arr){
for(int p : arr){
System.out.print(p+"\t");
}
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind union = new UnionFind(n);
System.out.println("初始parent:");
union.printArr(union.parent);
System.out.println("初始weight:");
union.printArr(union.weight);
System.out.println("连接了5 6 之后的parent:");
union.unionElements(5, 6);
union.printArr(union.parent);
System.out.println("连接了5 6 之后的weight:");
union.printArr(union.weight);
System.out.println("连接了1 2 之后的parent:");
union.unionElements(1, 2);
union.printArr(union.parent);
System.out.println("连接了1 2 之后的weight:");
union.printArr(union.weight);
System.out.println("连接了2 3 之后的parent:");
union.unionElements(2, 3);
union.printArr(union.parent);
System.out.println("连接了2 3 之后的weight:");
union.printArr(union.weight);
System.out.println("连接了1 4 之后的parent:");
union.unionElements(1, 4);
union.printArr(union.parent);
System.out.println("连接了1 4 之后的weight:");
union.printArr(union.weight);
System.out.println("连接了1 5 之后的parent:");
union.unionElements(1, 5);
union.printArr(union.parent);
System.out.println("连接了1 5 之后的weight:");
union.printArr(union.weight);
System.out.println("1 6 是否连接:" + union.isConnected(1, 6));
System.out.println("1 8 是否连接:" + union.isConnected(1, 8));
}
}
使用height的情况
public class UnionFind {
private int[] parent;
private int[] height;
int size;
public UnionFind(int size) {
this.size = size;
this.parent = new int[size];
this.height = new int[size];
// 在初始化分组的同时也初始化height
for (int i = 0; i < size; i++) {
parent[i] = i;
height[i] = 1;
}
}
public int find(int element) {
while (element != parent[element]) {
element = parent[element];
}
return element;
}
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public void unionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
if (height[firstRoot] < height[secondRoot]) {
parent[firstRoot] = secondRoot;
} else if (height[firstRoot] > height[secondRoot]) {
parent[secondRoot] = firstRoot;
} else {
/*
如果要合并的两个集合高度一样,那么随意选一个作为根
我这里选的是让secondRoot作为新集合的根。
然后secondRoot高度高了一层,所以+1
*/
parent[firstRoot] = secondRoot;
height[secondRoot] += 1;
}
}
private void printArr(int[] arr){
for(int p : arr){
System.out.print(p+"\t");
}
System.out.println();
}
public static void main(String[] args) {
int n = 10;
UnionFind union = new UnionFind(n);
System.out.println("初始parent:");
union.printArr(union.parent);
System.out.println("初始height:");
union.printArr(union.height);
System.out.println("连接了5 6 之后的parent:");
union.unionElements(5, 6);
union.printArr(union.parent);
System.out.println("连接了5 6 之后的height:");
union.printArr(union.height);
System.out.println("连接了1 2 之后的parent:");
union.unionElements(1, 2);
union.printArr(union.parent);
System.out.println("连接了1 2 之后的height:");
union.printArr(union.height);
System.out.println("连接了2 3 之后的parent:");
union.unionElements(2, 3);
union.printArr(union.parent);
System.out.println("连接了2 3 之后的height:");
union.printArr(union.height);
System.out.println("连接了1 4 之后的parent:");
union.unionElements(1, 4);
union.printArr(union.parent);
System.out.println("连接了1 4 之后的height:");
union.printArr(union.height);
System.out.println("连接了1 5 之后的parent:");
union.unionElements(1, 5);
union.printArr(union.parent);
System.out.println("连接了1 5 之后的height:");
union.printArr(union.height);
System.out.println("1 6 是否连接:" + union.isConnected(1, 6));
System.out.println("1 8 是否连接:" + union.isConnected(1, 8));
}
}
下面略加修改代码,使之可以计算分组的数量,并对路径进行了两种优化
class UnionFind {
private int[] parent;
private int[] weight;
private int size;//代表并查集中元素个数
private int groups;//代表并查集中有多少个集合(小组)
public UnionFind(int size) {
this.parent = new int[size];
this.weight = new int[size];
this.size = size;
// 初始化分组数量
this.groups = size;//因为初始的时候每个人自成一组,所以有多少人就有多少组
for (int i = 0; i < size; i++) {
this.parent[i] = i;
this.weight[i] = 1;
}
}
/* find第一种写法 */
public int find(int element) {
while (element != parent[element]) {
// 路径对折,只压缩一层,改变从e 到根节点路径上每隔
// 一个节点(除了根和其子节点)的指针,使其指向各自的祖父节点。
parent[element] = parent[parent[element]];
element = parent[element];
}
return element;
}
/* find第二种写法
public int find(int element) {
int fa;
while (element != parent[element]) {
// 路径分割,只压缩一层,改变从e 到根节点路径上每个
// 节点(除了根和其子节点)的指针,使其指向各自的祖父节点。
fa = parent[element];
parent[element] = parent[parent[element]];
element = fa;
}
return element;
}
*/
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public void unionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
//如果已经属于同一个集合了,就不用再合并了。
if (firstRoot == secondRoot) {
return;
}
if (weight[firstRoot] > weight[secondRoot]) {
parent[secondRoot] = firstRoot;
weight[firstRoot] += weight[secondRoot];
} else {//weight[firstRoot] <= weight[secondRoot]
parent[firstRoot] = secondRoot;
weight[secondRoot] += weight[firstRoot];
}
//合并 firstElement 和 secondElement 所在的两个组后,就少了一组。
this.groups--;
}
// 获取分组的数量
public int getGroups() {
return this.groups;
}
}
最后再说一下路径压缩,所谓路径压缩,是因为分组形成的树,高度不一定,分组内的元素要找到根结点,可能要进行若干次判断,所以我们想让所有的非根结点都直接与根结点相连,这样最多两次判断,就可以找到根结点,下面给出最终代码
public class UnionFind
{
private int[] parent;
private int[] weight;
private int size;//代表并查集中元素个数
private int groups;//代表并查集中有多少个集合(小组)
public UnionFind(int size) {
this.parent = new int[size];
this.weight = new int[size];
this.size = size;
this.groups = size;//因为初始的时候每个人自成一组,所以有多少人就有多少组
for (int i = 0; i < size; i++) {
this.parent[i] = i;
this.weight[i] = 1;
}
}
// 返回分组的根结点,一行代码
public int find(int x) {
return x != parent[x] ? parent[x] = find(parent[x]) : parent[x];
}
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public void unionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
//如果已经属于同一个集合了,就不用再合并了。
if (firstRoot == secondRoot) {
return;
}
if (weight[firstRoot] > weight[secondRoot]) {
parent[secondRoot] = firstRoot;
weight[firstRoot] += weight[secondRoot];
} else {//weight[firstRoot] <= weight[secondRoot]
parent[firstRoot] = secondRoot;
weight[secondRoot] += weight[firstRoot];
}
//合并 firstElement 和 secondElement 所在的两个组后,就少了一组。
this.groups--;
}
public int getGroups() {
return this.groups;
}
}
注:一行代码搞定find和union函数
int find(int x){
return x != parent[x] ? parent[x] = find(parent[x]) : parent[x];
}
void union(int x, int y){
parent[find(y)] = find(x);
}
亲爱的读者:有时间可以点赞评论一下
全部评论