并查集
并查集
概述
- 作用：支持集合的快速合并与查找，时间复杂度为O（1）
- 两个基本方法：isSameSet：两个集合是否属于同一个集合，union：合并两个集合
- 传统的数据结构无法同时支持两种方法的快速化。例如：链表结构可以支持快速合并，却无法支持快速查找；哈希表：支持快速查找，却无法支持快速合并
解决方案
（1）开始每个节点的指针指向自己
（3）若多个集合合并，要让节点数少的顶点指向节点数多的顶点 ，例如union(1，2）就是要改变2的指针
（4）isSameSet：方法就可以去遍历顶部节点是否相同来判断，例在上图中：isSameSet(2，6)返回值就是false；若在下图中：isSameSet(2，6)返回值就是true。
（5）优化问题（路径压缩）：若链过长在使用isSameSet的时候会导致时间复杂度上升，使用findHead方法，在过程中将每个节点的父节点最终都变成最高的顶点
使用findHead后将1，2直接与顶点相连
实现
public static class Element<V>{ //对样本的包装，形成元素 //内部使用Element //外部使用V，泛型类的使用 public V value; public Element(V value){ this.value = value; } } public static class UnionFindSet<V>{ //并查集 public HashMap<V, Element<V>> elementMap; //key是样本，value是样本对应进行包装后的元素，方便判断样本是否存在 public HashMap<Element<V>, Element<V>> fatherMap; //key是元素，value是该元素的父元素 public HashMap<Element<V>, Integer> sizeMap; //key是某个集合的顶点元素（代表集合），value是该集合的大小 public UnionFindSet(List<V> list){ //初始化：要求用户提供集合 elementMap = new HashMap<>(); fatherMap = new HashMap<>(); sizeMap = new HashMap<>(); for (V value : list){ //遍历集合 //开始都各自为一个集合 Element<V> element = new Element<>(value); elementMap.put(value, element); fatherMap.put(element, element); sizeMap.put(element, 1); } } private Element<V> findHead(Element<V> element){ //找到一个集合的顶点元素 //并且将该节点以及其上节点的父节点全部改成顶点节点 Stack<Element<V>> stack = new Stack<>(); while (element != fatherMap.get(element)){ //遍历到顶点元素 stack.push(element); element = fatherMap.get(element); } while (!stack.isEmpty()){ //修改该节点以及其上节点的父节点全部改成顶点节点 fatherMap.put(stack.pop(), element); } return element; } public boolean isSameSet(V a, V b){ //判断a，b是否属于同一集合 if (elementMap.containsKey(a) && elementMap.containsKey(b)){ //a，b均存在集合中，判断顶点元素是否相同 return findHead(elementMap.get(a)) == findHead(elementMap.get(b)); } return false; } public void union(V a, V b){ if (!elementMap.containsKey(a) || ! elementMap.containsKey(b)){ //若不存在集合中 return; } if (isSameSet(a, b)){ //属于同一集合 return; } //a，b的顶元素 Element<V> aH = findHead(elementMap.get(a)); Element<V> bH = findHead(elementMap.get(b)); //a，b中较大的集合与较小集合的区分 Element<V> big = sizeMap.get(aH) >= sizeMap.get(bH) ? aH : bH; Element<V> small = big == aH ? bH : aH; //较小的顶点连到较大的顶点 fatherMap.put(small, big); sizeMap.put(big, sizeMap.get(small) + sizeMap.get(big)); sizeMap.remove(small); } }
题目：岛问题
思路
遍历矩阵将所有可以相连的 1 全部变成 2 ，有几次变成 2 的过程就有几个岛
public static int countIslands(int[][] land){ if (land == null || land[0] == null){ return 0; } int x = land.length; int y = land[1].length; int res = 0; for (int i = 0; i < x; i++){ for (int j = 0; j < y; j++){ if (land[i][j] == 1){ //遍历矩阵 res++; infect(land, i, j, x, y); } } } return res; } public static void infect(int[][] land, int i, int j, int x, int y){ //将相连为 1的全部变成 2 if (i < 0 || i >= x || j < 0 || j >= y || land[i][j] != 1){ //结束条件 return; } land[i][j] = 2; //向四周遍历 infect(land, i + 1, j, x, y); infect(land, i - 1, j, x, y); infect(land, i, j + 1, x, y); infect(land, i, j - 1, x, y); } public static void main(String[] args) { int[][] land = {{0, 0, 1, 0, 1, 0}, {1, 1, 1, 0, 1, 0}, {1, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0}}; System.out.println(countIslands(land)); }
- 结果演示：
- 时间复杂度：O（ X * Y）x：为矩阵的高度， y：为矩阵的宽度
进阶：并查集的应用
（1）若图特别大的情况下，将图进行划分，划分后的图便可以在子图中同时处理数据，达到并行的效果
（2）但是划分图会可能造成岛的增加
（3）需要对边界进行处理，将边界在同一次相连的过程中变成到的点作为一个集合
（4）将分割后的子图相连的点经行判断，若子图的点有相邻的检查是否属性一个集合，若不属性，两集合合并，并且图的数目减一
