并查集

前言如果能够科学上网，英文水平良好，建议登入cousera进行学习。平台上有完整的作业提交平台，对提交的作业有详细的性能诊断和反馈；有课程各种资源；有课程讨论。在课程提问区提问还会收到导师的回答。链接：Algorithms, Part IAlgorithms, Part II《算法》第四版：testbook链接(英文)：https://algs4.cs.princeton.ed…主要内容并查集是一种树形的数据结构，通过这种数据结构能够有效处理不相交集合间的合并(union)及查询(find)问题。比如动态连通性问题。这种数据结构主要涉及两个操作：Find：查询元素属于哪一个子集。此操作还可以用来确定两个元素是否属于同一子集。Union：将两个子集合并成到一个集合中。1. 动态连通性问题(dynamic connectivity)动态连通性的应用很广泛：比如网络诊断：网络中的两台计算机是否连通，社交网络中的两个人是否存在交集，芯片中的电路元件连通性等等。场景：对象数码照片：像素网络：计算机社交网络：人…在编程中我们会对所有这些不同类型的对象进行简单的编号（0 – N-1），这样方便利用整数作为数组的索引号，快速地访问每个对象的相关信息，还可以忽略与并查集问题不相关的很多细节。1.1 建立问题模型给定一个有N个性质相同的对象的集合问题大体上所需要的基本操作：连通（Union）：两个对象间可以连通连通性的查询（Find/connected）：查询两个对象之间是否有连通路径如下图，通过Union(x,y)命令给若干对象之间建立连通路径；通过connected(x,y)命令查看两个对象是否连通。我们的任务就是对于给定的对象集合高效地实现这两个命令。因为合并命令和连通命令交叉混合，所以我们还有一个任务是我们的解决方案能支持大量对象和大量混合操作的高效处理。1.2 提取连通性质的抽象性1.2.1 假设“连接到（is connected to）”是一个具有下边关系性质的等价关系：那么它会有如下一些性质：反身：每个对象都能连接到自己 （p is connected to p）对称：如果p与q连通，那么q也与p连通传递：如果p与q连通，q与r连通，那么p与r连通这些性质都是直观自然的。明确了这些等价关系后，下面给出“连通分量”的定义。1.2.2 连通分量（connected components）有了等价关系后，一个对象和链接的集合就分裂为子集，这些子集就为连通分量。连通分量是互相连接对象的最大集合，并且连通分量之间并不连通。如下图左边，有3个连通分量。我们的算法通过维护连通分量来获得效率，并使用连通分量来高效地应答接收的请求。有了连通分量的概念后，并查集（即动态联通问题）要实现的操作有:Find 查找: 查找检查两个对象是否在相同的连通分量中Union 合并命令：将包含两个对象的连通分量合并为一个子集（一个连通分量）。如下图。1.3 Union-find 数据类型（API)从之前的讨论我们得到了一个数据类型，在编程的概念中，它是为了解决问题我们想要实现的方法和规范。在Java的模型中，创建一个类来表示这些方法和规范。其中包含：构造函数：参数是对象的数量，根据对象的数量建立数据结构两个操作：a) 实现合并； b) 连接超找，返回一个布尔值（逻辑变量：真/假）在实现算法的过程中，应该明确算法在以下的情况下也必须高效：对象和操作的数量都可能是巨大的合并和连接的混合操作也会非常频繁在处理更深层的问题之前，通过设计一个测试客户端用于检查API，确保任何一种实现都执行了我们希望他执行的操作。如下图，客户端从标准输入（tinyUF）中读取信息。首先读取“10”这个整数，表示要处理的对象的数量，并创建一个UF对象。然后只要标准输入中还有输入，客户端将从输入读取两个整数，如果他们没有连通，将他们连通并输出。否则忽略这条输入。2. 实现动态连通性问题的算法也可以说就是实现并查集的算法。这些算法的目的并不是给出两个对象的连通路径是什么，而是回答是否存在这么一条路径。虽然给出两个对象相连的路径也回答了是否连通的问题，但是于我们的目的而言不是直接契合，效率也不高。使用并查集数据结构是一个不错的策略。实现动态连通性问题的算法有：quick-find 快速查找 （QF）quick-union 快速合并 （QU）Weighted quick-union 加权优化 （WQU）Quick union with path compression 路径压缩优化（QUPC）两种优化可以结合一起使用，以下简称"WQUPC",即 weighted QU + path compression2.1 quick-find快速查找算法也称为“贪心算法”。（简单来说贪心算法就是在对问题求解时总是作出当前看来是最好的选择，只得出在某种意义上的局部最优解，不一定能得到整体最优解）2.1.1 Qinck-find 简介Qinck-find数据结构：简单的对象索引整数数组 id[](size = n)(具体来说就是当且仅当两个对象 p 与 q 是在数组中的id一样，那么他们即为连通)如图：0,5,6在一个连通分量；1,2,7在一个连通分量；3,4,8,9连通由此：Find：检查 p 和 q 是否 id 值相等Union：合并两个给定对象的的两个连通分量，即需要将与给定对象之一（p）有相同 id 的所有对象的 id 值都变为另一个给定对象（q）的 id 值如图经过 union(6,1), 通过合并6和1,6所在的连通分量中的所有对象（0,5,6）的id值都变为1的 id 值（1）这个算法的主要问题是当进行合并操作是，遇往后，需要改变id值的操作就越多。2.1.2 Java实现：a) 构造器：建立一个私有化整数数组，并将对应索引的数组项设为索引值b) 连通判断：两个数组项的 id 值是否相等c) 合并操作：取出两个参数的 id 值，遍历整个数组，找到同第一个参数id值相同的所以id项，并将他们都赋值成第二个参数的id值。具体代码实现：QuickFindUF.java2.1.3 性能分析衡量因子：代码需要访问数组的次数增长量级构造函数初始化和合并操作时都需要遍历整个数组，所以他们必须以常数正比于N次访问数组（增长量级为N）查找的操作很快，只需要进行常数次比较（增长量级为1）算法的特点是查找很快，但是合并的代价太大，如果需要在N个对象上进行N次合并操作，访问数组就需要N的平方次增长量级的操作，这是不合理的。平方量级的时间太慢。对于大型问题不能接受平方时间的算法。随着计算机变得更快，平方时间算法实际会变得更慢，简单来说，假如计算机每秒能进行几十亿次的操作，这些计算机的主内存中有几十亿项，大约一秒钟的时间我们就可以访问主内存所有的项，现在希望算法对几十亿的对象进行几十亿的操作，快速查找算法需要访问数组大约10的18次方次，大概是30多年的计算时间。2.2 quick-union快速查找对于处理巨大问题太慢，所以第一个尝试是使用快速合并算法进行替换。快速合并的算法设计采用了所谓的“懒策略”，即尽量避免计算直到不得不进行计算。2.2.1 Quick-union简介Quick-union数据结构大小为N的整数数组 id[]（size = N）这里的数组看做是一片森林（即一组树的集合），数组中的每一项包含它在树中的父节点。下图可以看出3的父节点是4, 4的父结点是9，9的父节点是它自身，也就是9是这颗树的父节点。从某个对象出发，一路从父节点向上就能找到根节点。由此：Find：查找两个对象（p & q）的根节点是否相等Union：合并两个对象的连通分量，即把 p 的根节点的值设为 q 的根节点的值。如图， union(3,5) 即把3的根节点(9)的id值设为5的根节点(6)的id值。由此，3所在的连通分量与5所在的连通分量进行了合并。可以看出合并两个连通分量只需要改数组中的一个值，但查找根节点会需要多一些操作。2.2.2 Java实现：a) 构造器与Quick-find相同b) 私有方法root()通过回溯实现寻找根节点c) 通过私有方法实现查找操作（是否连通操作）。通过判断两个对象的根节点是否相同即得出返回d) 合并操作就是找到两个对象的根节点，并将第一个根节点的id值设为第二个对象根节点的id值详细实现：QuickUnionUF.java2.2.3 性能分析：衡量因子：代码需要访问数组的次数增长量级快速合并的算法依旧很慢。快速查找的缺点在于树可能太高，这样对于查找操作的代价太大，最坏的情况需要N次数组访问才能找到某个对象的根节点。（合并操作的统计也包含了查找跟的操作）3 quick-union算法改进3.1 加权QF 和 QU 都不能支持巨大的动态连通性问题，一种有效的改进办法：加权 Weighted quick-union之前说到了 QU 的缺点就是因为树太高会引起查找操作代价巨大，那么在实现QU算法的时候执行一些操作避免得到很高的树就是改进的一个思路。QU算法在合并两颗树的时候可能会把大树放在小树的下边，如此树会变高。为了避免合并后导致更高的树，让小树的根节点指向大树的根节点。由此保证所有的对象不会离根节点太远。可以通过加权的方式可以实现。WQU:跟踪每棵树中对象的个数将小树（对象所在的连通分量里的元素个数较少一方）的根节点设为大树的根节点的子节点Java 实现数据结构在QU的基础上添加一个额外的数组 size[i] 记录以该对象为根节点的树中的对象个数Find: 同QU一样，只需要检查根节点是否相同Union：通过 size[i] 先检查两颗树的大小，然后将小树的根节点设为大树的根节点，同时更新合并后连通分量中根节点项的size数组项的值完整实现：WeightedQuickUnionUF.java性能分析运行时间Find：与结点在树中的运行时间成正比Union：给出根节点后花费常量时间命题树中任意结点的深度上限为lgN(此lg以2为底数)证明理解这个命题的关键在于观察节点（此为X节点）的深度到底是在何时会增加a) 只有当T2的尺寸>=T1的尺寸的时候，T1和T2才会合并为一个连通分量，此时T1的深度（depth）才会增加b) 合并后T1的大小至少是原来的2倍，由此粗略估计，x的深度每增加1，则x所在的集合的大小变为原来的2倍c) 如果整个集合的大小为N，那么x所在的集合大小最大尺寸只能为N，那么从x=1开始，有12^depth=N –> depth = lgN 即树中任意节点的深度最多为lgN三种算法的性能对比如果N是100万，则lgN=20；如果N是10亿，lgN=30。加权的处理在代码上并不需要多少的修改，可是性能上却取得了很大的提升。3.2 路径压缩在经过加权处理后，还可以更进一步优化这个算法。此为添加路径压缩 Quick union with path compression 的操作。在试图寻找包含给定节点的树的根节点时，我们需要访问从该节点到根节点路径上的每个节点。那么，于此同时我们可以将访问到的所有节点的根节点顺便移动设置为他所在的树的根节点。 这需要付出常数的额外代价。如图：当我们找到P的根节点后，把9,6,3的根节点都设为0（1的根节点已经是树的根节点）：变为 这里做的改变是：将路径上的每个节点指向它在路径上的祖父节点，这种实现并没有把树完全展平，但在实际应用中两种方式都超不多一样好。将树完全展平：find(int p) 方法回溯一次路径找到根节点，然后再回溯一次将树展平，参考：QuickUnionPathCompressionUF.java性能分析以证明：有N个对象，M个合并与查找操作的任意序列，需要访问数组最多为 c( N + M lg N )次。lgN 是使N变为1所需要的对数的次数，叫迭代对数函数。在真实世界中可以认为lgN是一个小于5的数。这个证明可以不用深究，两种优化的代码实现参考：WeightedQuickUnionPathCompressionUF.java通过WQUPC的优化，之前的例子，假如要对10亿个对象进行10亿个操作，QF需要30年，现在只需要大概6秒。课后巩固（折日更新）Interview Questions 面试问题Programming Assignment: Percolation 编程练习IDE本人使用IntelliJ IDEA, jdk8需要使用的jar包：git地址： ...

题目Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)Example 1:[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.Example 2:[[0,0,0,0,0,0,0,0]]Given the above grid, return 0.Note: The length of each dimension in the given grid does not exceed 50.题目地址讲解一看这题我首先想到的就是并查集，只不过我们需要稍作改动，我们需要知道每个并查集的元素大小，所以我加入了一个size属性，而为了节省空间去掉了value属性。另外，我们还需要一个空间来存储DS结点，而且最好是很快的取出，所以我使用了hashmap来存，但key是一个整数元组（tuple），但java不能很方便的使用tuple，所以我直接变相的使用字符串来实现Key。java代码class Solution { public int maxAreaOfIsland(int[][] grid) { Map<String, DS> map = new HashMap<>(); for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[i].length;j++){ if(grid[i][j]==1){ DS ds = new DS(1); map.put(i+","+j, ds); if(i-1>=0 && grid[i-1][j]==1){ ds.union(map.get((i-1)+","+j), ds); } if(j-1>=0 && grid[i][j-1]==1){ ds.union(map.get(i+","+(j-1)), ds); } } } } int result = 0; for(String s:map.keySet()){ int size = map.get(s).find().size; if(result<size){ result = size; } } return result; } class DS{ // private int value; private DS parent; private int rank; private int size; public DS(int value){ // this.value = value; rank = 0; parent = this; size = 1; } public DS find(){ if(this.parent!=this){ this.parent = this.parent.find(); } return this.parent; } public void union(DS x, DS y){ DS xParent = x.find(); DS yParent = y.find(); if(xParent==yParent){ return; } if(xParent.rank>yParent.rank){ yParent.parent = xParent; xParent.size += yParent.size; }else if(xParent.rank<yParent.rank){ xParent.parent = yParent; yParent.size += xParent.size; }else{ xParent.parent = yParent; yParent.size += xParent.size; yParent.rank++; } } }} ...

题目In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, , or blank space. These characters divide the square into contiguous regions.(Note that backslash characters are escaped, so a \ is represented as “\”.)Return the number of regions.Example 1:Input:[ " /", “/ “]Output: 2Explanation: The 2x2 grid is as follows:Example 2:Input:[ " /”, " “]Output: 1Explanation: The 2x2 grid is as follows:Example 3:Input:[ “\/”, “/\"]Output: 4Explanation: (Recall that because \ characters are escaped, “\/” refers to /, and “/\” refers to /.)The 2x2 grid is as follows:Example 4:Input:[ “/\”, “\/"]Output: 5Explanation: (Recall that because \ characters are escaped, “/\” refers to /, and “\/” refers to /.)The 2x2 grid is as follows:Example 5:Input:[ “//”, “/ “]Output: 3Explanation: The 2x2 grid is as follows:Note:1 <= grid.length == grid[0].length <= 30grid[i][j] is either ‘/’, ‘', or ’ ‘.题目地址讲解这道题是关于图的题，用到了并查集这个数据结构。好久没用并查集了，我主要是参考了这个博客:https://zxi.mytechroad.com/bl…Java代码class Solution { public int regionsBySlashes(String[] grid) { int result = 0; int index=-1; List<DisJointSet> list = new ArrayList<>(); for(String s:grid){ for(Character c:s.toCharArray()){ for(int i=0;i<4;i++){ DisJointSet ds = new DisJointSet(); list.add(ds); } } } for(int j=0;j<grid.length;j++){ for(int i=0;i<grid[j].length();i++){ DisJointSet ds1 = list.get(++index); DisJointSet ds2 = list.get(++index); DisJointSet ds3 = list.get(++index); DisJointSet ds4 = list.get(++index); System.out.println(grid[j].charAt(i)); if(grid[j].charAt(i)==’ ‘){ DisJointSet.union(ds1, ds2); DisJointSet.union(ds2, ds3); DisJointSet.union(ds3, ds4); } if(grid[j].charAt(i)==’/’){ DisJointSet.union(ds1, ds4); DisJointSet.union(ds2, ds3); } if(grid[j].charAt(i)==’\’){ DisJointSet.union(ds1, ds2); DisJointSet.union(ds3, ds4); } if(i<grid[j].length()-1){ DisJointSet.union(ds2, list.get(index+4)); } if(j<grid.length-1){ DisJointSet.union(ds3, list.get(index+4*(grid[j].length()-1)+1)); } } } for(DisJointSet ds:list){ if(ds.find()==ds){ result++; } } return result; }}class DisJointSet{ public DisJointSet parent; public int rank; public DisJointSet(){ rank = 0; parent = this; } public DisJointSet find(){ if(parent!=this){ parent = parent.find(); } return parent; } public static void union(DisJointSet ds1, DisJointSet ds2){ DisJointSet ds1Root = ds1.find(); DisJointSet ds2Root = ds2.find(); if(ds1Root!=ds2Root){ if(ds1Root.rank>ds2Root.rank){ ds2Root.parent = ds1Root; }else if(ds1Root.rank<ds2Root.rank){ ds1Root.parent = ds2Root; }else if(ds1Root.rank==ds2Root.rank){ ds1Root.parent = ds2Root; ds2Root.rank++; } } } } ...