并查集
并查集的功能
并查集是一种树型的数据结构，在一些有N个元素的集合的应用问题中，并查集需要收集好所有的数据样本（不支持动态添加新的元素），通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
并查集的主要功能有两个：
- 判断元素A所在的集合是否和元素B所在的集合是同一个集合
- 元素A所在的集合与元素B所在的集合合并
并查集的初始化是将样本量为N的数据的每个元素构成一个单元素的集合
每一个元素作为一个节点，同时自己指向自己，成为 标记节点 ,作为一个单元素构成的集合。
isSameSet
在并查集中，判断A所在的集合是否和B所在的集合是同一个集合，假使有并查集的结构如下：
并查集中，如果两个节点的标记节点为同一个节点那么这两个节点所在的集合就是同一个集合。
例如：
节点2和节点3所在的集合是否为同一个集合，回答是，因为2和3的标记节点均为1。
节点3和节点5所在的集合是否为同一个集合，回答不是，因为5所在的集合的标记节点为5，3所在的集合的标记节点为1，所以不是同一集合。
扁平化处理
还是对于上面的图而言，查询节点4和节点8所在的集合是否为同一个集合，很显然节点4和8的标记节点并不相同所以所在的集合并非同一个集合，但是在查询节点4时，向上遍历的路径也就是遍历的高度并不为1，为了提升下次查询的效率，我们将把查询的节点4直接指向它的标记节点再返回它的标记节点，即：
在扁平化处理后，会提升下次查询的效率。
union(A,B)
将节点4所在的集合和节点8所在的集合合并
首先，先要判断节点4和节点8的标记节点是否是同一节点，如果为同一节点，则说明两个节点所在的集合为同一集合，不发生合并行为，4节点的标记节点为1，8节点的标记节点为5说明两个节点所在的集合并不是同一个集合，发生unoin行为，5为标记节点的集合节点总数为2，1为标记节点的集合节点总数为5，所以少数向多数合并
并查集的代码实现
代码实现如下：
import java.util.HashMap;
import java.util.List;
public class UnionFind {
public static class Node{
}
public static class UnionFindSet{
public HashMap<Node,Node> fatherMap; // key: current node ; value: father node
public HashMap<Node,Integer> sizeMap; // key: current node ; value: set node number
public UnionFindSet(List<Node> nodeList){
fatherMap = new HashMap<>();
sizeMap = new HashMap<>();
for(Node node : nodeList){
fatherMap.put(node,node); // 每个节点的标记节点为自身
sizeMap.put(node,1); // 每个节点所在的集合的节点总数为1
}
}
private Node findHead(Node node){
Node father = fatherMap.get(node);
if(father != node){
father = findHead(father);
}
fatherMap.put(node,father);
return father;
}
public boolean isSameSet(Node a,Node b){
return findHead(a) == findHead(b);
}
public void union(Node a,Node b){
if(a == null || b == null)
return;
Node aHead = findHead(a);
Node bHead = findHead(b);
if(aHead != bHead){
int aSetSize =sizeMap.get(aHead);
int bSetSize = sizeMap.get(bHead);
if(aSetSize < bSetSize){
fatherMap.put(aHead,bHead);
sizeMap.put(bHead,aSetSize + bSetSize);
}else{
fatherMap.put(bHead,aHead);
sizeMap.put(aHead,aSetSize + bSetSize);
}
}
}
}
}
岛问题
一个矩阵中只有0和1两种值
每个位置都可以和自己的上、下、左、右 四个位置相连；
如果有一片1连在一起，这个部分叫做一个岛，求一个 矩阵中有多少个岛？
举例：
0 0 1 0 1 0
1 1 1 0 1 0
1 0 0 1 0 0
0 0 0 0 0 0
在这样一个矩阵中有三个岛
问题解法：
设置一个感染方法，遍历矩阵，当遍历到矩阵当前元素值为“1”的时候，进入感染方法，感染方法可以让矩阵中的上下左右相邻为1的元素感染变为数值“2”，岛的数量+1，感染完成后，继续遍历，遍历到2和0的时候跳过，当又遍历到有“1”的元素时继续感染，岛的数量++ ... 代码如下：
public class IsLands {
public static int landsNum(int[][] matrix){
if(matrix == null || matrix[0] == null){
return 0;
}
int num = 0;
int row = matrix.length;
int column = matrix[0].length;
for(int i = 0;i < row;i++){
for(int j = 0;j < column;j++){
infect(matrix,i,j,row,column);
num++;
}
}
return num;
}
public static void infect(int[][] matrix,int rowIndex,int columnIndex,int row,int column){
if(rowIndex < 0 || rowIndex >= row || columnIndex < 0 || columnIndex >= column || matrix[rowIndex][columnIndex] != 1){
return;
}
matrix[rowIndex][columnIndex] = 2;
infect(matrix,rowIndex + 1,columnIndex,row,column);
infect(matrix,rowIndex - 1,columnIndex,row,column);
infect(matrix,rowIndex,columnIndex + 1,row,column);
infect(matrix,rowIndex,columnIndex - 1,row,column);
}
}
岛问题的思考
假设一个矩阵很大，需要使用多台机器并行计算，即：将这个矩阵分割成一个个的小块，如果还要获得整个大矩阵的岛的数量，应该怎么做？
如果有一个矩阵，被分成了左右两块，左边的那块矩阵获得岛的数量为2，右边的那块矩阵获得的岛的数量为2，那么整个矩阵岛的数量是4么？答案：不是的。岛的数量与矩阵及矩阵的边界有关，示例：
本示例中，左矩阵有2个岛，右矩阵也有2个岛，但是合在一起的矩阵 岛的总数为：2个
对于这样的一个问题，涉及到了两个元素所在的集合是否为同一个集合，那么最好的解决方法就是并查集
对于矩阵相交的边界如下：
1 | 1 左边的1属于集合A，右边的1属于集合C，这两个集合不是一个集合 岛总数-1,集合A与集合C union
1 | 1 集合A与集合C union后，这两个1属于一个集合
0 | 1
1 | 1 左边的1属于集合B，右边的1属于集合D，这个两个集合不是一个集合 岛总数-1，集合B与集合D union
1 | 0
所以岛的总数为2 + 2 - 2 = 2
两个矩阵合并后共有两个岛。
所以本题的解题思路为，将大矩阵分块，收集每个矩阵四边边界信息，将每块矩阵的岛总数相加通过并查集对岛总数做减法后，得到的值即为整个大矩阵岛的数量。