文章目录并查集并查集是一种树型的数据结构并查集结构1. 并查集的实现API设计UF(int N)构造方法实现union(int p,int q)合并方法实现代码测试案例 1 : 计算机网诺连接2. UF_Tree算法优化eleAndGourp数组API设计find(int p)查询方法实现union(int p,int q)合并方法实现代码优化后的性能分析3. 优化之-----路径压缩分析API设计代码案例 2 : 畅通工程需求:解题思路代码并查集并查集是一种树型的数据结构并查集是一种树型的数据结构 并查集可以高效地进行如下操作查询元素p和元素q是否属于同一组合并元素p和元素q所在的组并查集结构并查集也是一种树型结构但这棵树跟我们之前讲的二叉树、红黑树、B树等都不一样这种树的要求比较简单每个元素都唯一的对应一个结点每一组数据中的多个元素都在同一颗树中一个组中的数据对应的树和另外一个组中的数据对应的树之间没有任何联系元素在树中并没有子父级关系的硬性要求1. 并查集的实现API设计UF(int N)构造方法实现初始情况下每个元素都在一个独立的分组中所以初始情况下并查集中的数据默认分为N个组初始化数组eleAndGroup把eleAndGroup数组的索引看做是每个结点存储的元素把eleAndGroup数组每个索引处的值看做是该结点所在的分组那么初始化情况下i索引处存储的值就是iunion(int p,int q)合并方法实现如果p和q已经在同一个分组中则无需合并如果p和q不在同一个分组则只需要将p元素所在组的所有的元素的组标识符修改为q元素所在组的标识符即可分组数量-1代码packagemain.java.Algorithms.tree;publicclassUF{//记录结点元素和该元素所在分组的标识privateint[]eleAndGroup;//记录并查集中数据的分组个数privateintcount;//初始化并查集publicUF(intN){//初始化分组的数量,默认情况下有N个分组this.countN;//初始化eleAndGroup数组this.eleAndGroupnewint[N];//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素并且让每个索引处的值(该元素所在的组的标识符)就是该索引for(inti0;ieleAndGroup.length;i){eleAndGroup[i]i;}}//获取当前并查集中的数据有多少个分组publicintcount(){returncount;}//元素p所在分组的标识符publicintfind(intp){returneleAndGroup[p];}//判断并查集中元素p和元素q是否在同一分组中publicbooleanconnected(intp,intq){returnfind(p)find(q);}//把p元素所在分组和q元素所在分组合并publicvoidunion(intp,intq){//判断元素q和p是否已经在同一分组中如果已经在同一分组中则结束方法就可以了if(connected(p,q)){return;}//找到p所在分组的标识符intpGroupfind(p);//找到q所在分组的标识符intqGroupfind(q);//合并组让p所在组的所有元素的组标识符变为q所在分组的标识符for(inti0;ieleAndGroup.length;i){if(eleAndGroup[i]pGroup){eleAndGroup[i]qGroup;}}//分组个数-1this.count--;}}测试packagemain.java.Algorithms.tree;importjava.util.Scanner;publicclassUFTest{publicstaticvoidmain(String[]args){//创建并查集对象UFufnewUF(5);System.out.println(默认情况下并查集中有uf.count()个分组);//从控制台录入两个要合并的元素调用union方法合并观察合并后并查集中的分组是否减少ScannerscnewScanner(System.in);while(true){System.out.println(请输入第一个要合并的元素);intpsc.nextInt();System.out.println(请输入第二个要合并的元素);intqsc.nextInt();//判断这两个元素是否已经在同一组了if(uf.connected(p,q)){System.out.println(p元素和q元素已经在同一个组中了);continue;}uf.union(p,q);System.out.println(当前并查集中还有uf.count()个分组);}}}案例 1 : 计算机网诺连接如果我们并查集存储的每一个整数表示的是一个大型计算机网络中的计算机则我们就可以通过connected(intp,int q)来检测该网络中的某两台计算机之间是否连通如果连通则他们之间可以通信如果不连通则不能通信此时我们又可以调用union(int p,int q)使得p和q之间连通这样两台计算机之间就可以通信了。一般像计算机这样网络型的数据我们要求网络中的每两个数据之间都是相连通的也就是说我们需要调用很多次union方法使得网络中所有数据相连其实我们很容易可以得出如果要让网络中的数据都相连则我们至少要调用N-1次union方法才可以但由于我们的union方法中使用for循环遍历了所有的元素所以很明显我们之前实现的合并算法的时间复杂度是O(N^2)如果要解决大规模问题它是不合适的所以我们需要对算法进行优化。2. UF_Tree算法优化为了提升union算法的性能我们需要重新设计find方法和union方法的实现此时我们先需要对我们的之前数据结构中的eleAndGourp数组的含义进行重新设定eleAndGourp数组我们仍然让eleAndGroup数组的索引作为某个结点的元素eleAndGroup[i]的值不再是当前结点所在的分组标识而是该结点的父结点API设计find(int p)查询方法实现判断当前元素p的父结点eleAndGroup[p]是不是自己如果是自己则证明已经是根结点了如果当前元素p的父结点不是自己则让peleAndGroup[p]继续找父结点的父结点,直到找到根结点为止union(int p,int q)合并方法实现找到p元素所在树的根结点找到q元素所在树的根结点如果p和q已经在同一个树中则无需合并如果p和q不在同一个分组则只需要将p元素所在树根结点的父结点设置为q元素的根结点即可分组数量-1代码packagemain.java.Algorithms.tree;publicclassUF_Tree{//记录结点元素和该元素所在分组的标识privateint[]eleAndGroup;//记录并查集中数据的分组个数privateintcount;//初始化并查集publicUF_Tree(intN){//初始化分组的数量,默认情况下有N个分组this.countN;//初始化eleAndGroup数组this.eleAndGroupnewint[N];//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素并且让每个索引处的值(该元素所在的组的标识符)就是该索引for(inti0;ieleAndGroup.length;i){eleAndGroup[i]i;}}//获取当前并查集中的数据有多少个分组publicintcount(){returncount;}//判断并查集中元素p和元素q是否在同一分组中publicbooleanconnected(intp,intq){returnfind(p)find(q);}//元素p所在分组的标识符publicintfind(intp){while(true){if(peleAndGroup[p]){returnp;}peleAndGroup[p];}}//把p元素所在分组和q元素所在分组合并publicvoidunion(intp,intq){//找到p元素和q元素所在组对应的树的根结点intpRootfind(p);intqRootfind(q);//如果p和q已经在同一分组则不需要合并了if(pRootqRoot){return;}//让p所在的树的根结点的父结点为q所在树的根结点即可eleAndGroup[pRoot]qRoot;//组的数量-1this.count--;}}优化后的性能分析我们优化后的算法union如果要把并查集中所有的数据连通仍然至少要调用N-1次union方法但是我们发现union方法中已经没有了for循环所以union算法的时间复杂度由O(N^2)变为了O(N)。但是这个算法仍然有问题因为我们之前不仅修改了union算法还修改了find算法。我们修改前的find算法的时间复杂度在任何情况下都为O(1)但修改后的find算法在最坏情况下是O(N)在union方法中调用了find方法所以在最坏情况下union算法的时间复杂度仍然为O(N^2)。3. 优化之-----路径压缩分析UF_Tree中最坏情况下union算法的时间复杂度为O(N^2)其最主要的问题在于最坏情况下树的深度和数组的大小一样如果我们能够通过一些算法让合并时生成的树的深度尽可能的小就可以优化find方法。之前我们在union算法中合并树的时候将任意的一棵树连接到了另外一棵树这种合并方法是比较暴力的如果我们把并查集中每一棵树的大小记录下来然后在每次合并树的时候把较小的树连接到较大的树上就可以减小树的深度。只要我们保证每次合并都能把小树合并到大树上就能够压缩合并后新树的路径这样就能提高find方法的效率。为了完成这个需求我们需要另外一个数组来记录存储每个根结点对应的树中元素的个数并且需要一些代码调整数组中的值。API设计代码packagemain.java.Algorithms.tree;publicclassUF_Tree_Weighted{//记录结点元素和该元素所在分组的标识privateint[]eleAndGroup;//记录并查集中数据的分组个数privateintcount;//用来存储每一个根结点对应的树中保存的结点的个数privateint[]sz;//初始化并查集publicUF_Tree_Weighted(intN){//初始化分组的数量,默认情况下有N个分组this.countN;//初始化eleAndGroup数组this.eleAndGroupnewint[N];//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素并且让每个索引处的值(该元素所在的组的标识符)就是该索引for(inti0;ieleAndGroup.length;i){eleAndGroup[i]i;}this.sznewint[N];//默认情况下sz中每个索引处的值都是1for(inti0;isz.length;i){sz[i]1;}}//获取当前并查集中的数据有多少个分组publicintcount(){returncount;}//判断并查集中元素p和元素q是否在同一分组中publicbooleanconnected(intp,intq){returnfind(p)find(q);}//元素p所在分组的标识符publicintfind(intp){while(true){if(peleAndGroup[p]){returnp;}peleAndGroup[p];}}//把p元素所在分组和q元素所在分组合并publicvoidunion(intp,intq){//找到p元素和q元素所在组对应的树的根结点intpRootfind(p);intqRootfind(q);//如果p和q已经在同一分组则不需要合并了if(pRootqRoot){return;}//判断proot对应的树大还是qroot对应的树大最终需要把较小的树合并到较大的树中if(sz[pRoot]sz[qRoot]){eleAndGroup[pRoot]qRoot;sz[qRoot]sz[pRoot];}else{eleAndGroup[qRoot]pRoot;sz[pRoot]sz[qRoot];}//组的数量-1this.count--;}}案例 2 : 畅通工程需求:某省调查城镇交通状况得到现有城镇道路统计表表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通但不一定有直接的道路相连只要互相间接通过道路可达即可。问最少还需要建设多少条道路在我们的测试数据文件夹中有一个trffic_project.txt文件它就是诚征道路统计表下面是对数据的解释总共有20个城市目前已经修改好了7条道路问还需要修建多少条道路才能让这20个城市之间全部相通解题思路创建一个并查集UF_Tree_Weighted(20);分别调用union(0,1),union(6,9),union(3,8),union(5,11),union(2,12),union(6,10),union(4,8)表示已经修建好的道路把对应的城市连接起来如果城市全部连接起来那么并查集中剩余的分组数目为1所有的城市都在一个树中所以只需要获取当前并查集中剩余的数目减去1就是还需要修建的道路数目代码packagemain.java.Algorithms.tree;importjava.io.BufferedReader;importjava.io.InputStreamReader;publicclassTraffic_Project_Test{publicstaticvoidmain(String[]args)throwsException{//构建一个缓冲读取流BufferedReaderBufferedReaderbrnewBufferedReader(newInputStreamReader(Traffic_Project_Test.class.getClassLoader().getResourceAsStream(traffic_project.txt)));//读取第一行数据20inttotalNumberInteger.parseInt(br.readLine());//构建一个并查集对象main.java.Algorithms.tree.UF_Tree_Weighted ufnewmain.java.Algorithms.tree.UF_Tree_Weighted(totalNumber);//读取第二行数据7introadNumberInteger.parseInt(br.readLine());//循环读取7条道路for(inti1;iroadNumber;i){Stringlinebr.readLine();//0 1String[]strline.split( );intpInteger.parseInt(str[0]);intqInteger.parseInt(str[1]);//调用并查集对象的union方法让两个城市相通uf.union(p,q);}//获取当前并查集中分组的数量-1就可以得到还需要修建的道路的数目introadsuf.count()-1;System.out.println(还需要修建roads条道路才能实现畅通工程);}} 树--12---并查集
文章目录并查集并查集是一种树型的数据结构并查集结构1. 并查集的实现API设计UF(int N)构造方法实现union(int p,int q)合并方法实现代码测试案例 1 : 计算机网诺连接2. UF_Tree算法优化eleAndGourp数组API设计find(int p)查询方法实现union(int p,int q)合并方法实现代码优化后的性能分析3. 优化之-----路径压缩分析API设计代码案例 2 : 畅通工程需求:解题思路代码并查集并查集是一种树型的数据结构并查集是一种树型的数据结构 并查集可以高效地进行如下操作查询元素p和元素q是否属于同一组合并元素p和元素q所在的组并查集结构并查集也是一种树型结构但这棵树跟我们之前讲的二叉树、红黑树、B树等都不一样这种树的要求比较简单每个元素都唯一的对应一个结点每一组数据中的多个元素都在同一颗树中一个组中的数据对应的树和另外一个组中的数据对应的树之间没有任何联系元素在树中并没有子父级关系的硬性要求1. 并查集的实现API设计UF(int N)构造方法实现初始情况下每个元素都在一个独立的分组中所以初始情况下并查集中的数据默认分为N个组初始化数组eleAndGroup把eleAndGroup数组的索引看做是每个结点存储的元素把eleAndGroup数组每个索引处的值看做是该结点所在的分组那么初始化情况下i索引处存储的值就是iunion(int p,int q)合并方法实现如果p和q已经在同一个分组中则无需合并如果p和q不在同一个分组则只需要将p元素所在组的所有的元素的组标识符修改为q元素所在组的标识符即可分组数量-1代码packagemain.java.Algorithms.tree;publicclassUF{//记录结点元素和该元素所在分组的标识privateint[]eleAndGroup;//记录并查集中数据的分组个数privateintcount;//初始化并查集publicUF(intN){//初始化分组的数量,默认情况下有N个分组this.countN;//初始化eleAndGroup数组this.eleAndGroupnewint[N];//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素并且让每个索引处的值(该元素所在的组的标识符)就是该索引for(inti0;ieleAndGroup.length;i){eleAndGroup[i]i;}}//获取当前并查集中的数据有多少个分组publicintcount(){returncount;}//元素p所在分组的标识符publicintfind(intp){returneleAndGroup[p];}//判断并查集中元素p和元素q是否在同一分组中publicbooleanconnected(intp,intq){returnfind(p)find(q);}//把p元素所在分组和q元素所在分组合并publicvoidunion(intp,intq){//判断元素q和p是否已经在同一分组中如果已经在同一分组中则结束方法就可以了if(connected(p,q)){return;}//找到p所在分组的标识符intpGroupfind(p);//找到q所在分组的标识符intqGroupfind(q);//合并组让p所在组的所有元素的组标识符变为q所在分组的标识符for(inti0;ieleAndGroup.length;i){if(eleAndGroup[i]pGroup){eleAndGroup[i]qGroup;}}//分组个数-1this.count--;}}测试packagemain.java.Algorithms.tree;importjava.util.Scanner;publicclassUFTest{publicstaticvoidmain(String[]args){//创建并查集对象UFufnewUF(5);System.out.println(默认情况下并查集中有uf.count()个分组);//从控制台录入两个要合并的元素调用union方法合并观察合并后并查集中的分组是否减少ScannerscnewScanner(System.in);while(true){System.out.println(请输入第一个要合并的元素);intpsc.nextInt();System.out.println(请输入第二个要合并的元素);intqsc.nextInt();//判断这两个元素是否已经在同一组了if(uf.connected(p,q)){System.out.println(p元素和q元素已经在同一个组中了);continue;}uf.union(p,q);System.out.println(当前并查集中还有uf.count()个分组);}}}案例 1 : 计算机网诺连接如果我们并查集存储的每一个整数表示的是一个大型计算机网络中的计算机则我们就可以通过connected(intp,int q)来检测该网络中的某两台计算机之间是否连通如果连通则他们之间可以通信如果不连通则不能通信此时我们又可以调用union(int p,int q)使得p和q之间连通这样两台计算机之间就可以通信了。一般像计算机这样网络型的数据我们要求网络中的每两个数据之间都是相连通的也就是说我们需要调用很多次union方法使得网络中所有数据相连其实我们很容易可以得出如果要让网络中的数据都相连则我们至少要调用N-1次union方法才可以但由于我们的union方法中使用for循环遍历了所有的元素所以很明显我们之前实现的合并算法的时间复杂度是O(N^2)如果要解决大规模问题它是不合适的所以我们需要对算法进行优化。2. UF_Tree算法优化为了提升union算法的性能我们需要重新设计find方法和union方法的实现此时我们先需要对我们的之前数据结构中的eleAndGourp数组的含义进行重新设定eleAndGourp数组我们仍然让eleAndGroup数组的索引作为某个结点的元素eleAndGroup[i]的值不再是当前结点所在的分组标识而是该结点的父结点API设计find(int p)查询方法实现判断当前元素p的父结点eleAndGroup[p]是不是自己如果是自己则证明已经是根结点了如果当前元素p的父结点不是自己则让peleAndGroup[p]继续找父结点的父结点,直到找到根结点为止union(int p,int q)合并方法实现找到p元素所在树的根结点找到q元素所在树的根结点如果p和q已经在同一个树中则无需合并如果p和q不在同一个分组则只需要将p元素所在树根结点的父结点设置为q元素的根结点即可分组数量-1代码packagemain.java.Algorithms.tree;publicclassUF_Tree{//记录结点元素和该元素所在分组的标识privateint[]eleAndGroup;//记录并查集中数据的分组个数privateintcount;//初始化并查集publicUF_Tree(intN){//初始化分组的数量,默认情况下有N个分组this.countN;//初始化eleAndGroup数组this.eleAndGroupnewint[N];//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素并且让每个索引处的值(该元素所在的组的标识符)就是该索引for(inti0;ieleAndGroup.length;i){eleAndGroup[i]i;}}//获取当前并查集中的数据有多少个分组publicintcount(){returncount;}//判断并查集中元素p和元素q是否在同一分组中publicbooleanconnected(intp,intq){returnfind(p)find(q);}//元素p所在分组的标识符publicintfind(intp){while(true){if(peleAndGroup[p]){returnp;}peleAndGroup[p];}}//把p元素所在分组和q元素所在分组合并publicvoidunion(intp,intq){//找到p元素和q元素所在组对应的树的根结点intpRootfind(p);intqRootfind(q);//如果p和q已经在同一分组则不需要合并了if(pRootqRoot){return;}//让p所在的树的根结点的父结点为q所在树的根结点即可eleAndGroup[pRoot]qRoot;//组的数量-1this.count--;}}优化后的性能分析我们优化后的算法union如果要把并查集中所有的数据连通仍然至少要调用N-1次union方法但是我们发现union方法中已经没有了for循环所以union算法的时间复杂度由O(N^2)变为了O(N)。但是这个算法仍然有问题因为我们之前不仅修改了union算法还修改了find算法。我们修改前的find算法的时间复杂度在任何情况下都为O(1)但修改后的find算法在最坏情况下是O(N)在union方法中调用了find方法所以在最坏情况下union算法的时间复杂度仍然为O(N^2)。3. 优化之-----路径压缩分析UF_Tree中最坏情况下union算法的时间复杂度为O(N^2)其最主要的问题在于最坏情况下树的深度和数组的大小一样如果我们能够通过一些算法让合并时生成的树的深度尽可能的小就可以优化find方法。之前我们在union算法中合并树的时候将任意的一棵树连接到了另外一棵树这种合并方法是比较暴力的如果我们把并查集中每一棵树的大小记录下来然后在每次合并树的时候把较小的树连接到较大的树上就可以减小树的深度。只要我们保证每次合并都能把小树合并到大树上就能够压缩合并后新树的路径这样就能提高find方法的效率。为了完成这个需求我们需要另外一个数组来记录存储每个根结点对应的树中元素的个数并且需要一些代码调整数组中的值。API设计代码packagemain.java.Algorithms.tree;publicclassUF_Tree_Weighted{//记录结点元素和该元素所在分组的标识privateint[]eleAndGroup;//记录并查集中数据的分组个数privateintcount;//用来存储每一个根结点对应的树中保存的结点的个数privateint[]sz;//初始化并查集publicUF_Tree_Weighted(intN){//初始化分组的数量,默认情况下有N个分组this.countN;//初始化eleAndGroup数组this.eleAndGroupnewint[N];//初始化eleAndGroup中的元素及其所在的组的标识符,让eleAndGroup数组的索引作为并查集的每个结点的元素并且让每个索引处的值(该元素所在的组的标识符)就是该索引for(inti0;ieleAndGroup.length;i){eleAndGroup[i]i;}this.sznewint[N];//默认情况下sz中每个索引处的值都是1for(inti0;isz.length;i){sz[i]1;}}//获取当前并查集中的数据有多少个分组publicintcount(){returncount;}//判断并查集中元素p和元素q是否在同一分组中publicbooleanconnected(intp,intq){returnfind(p)find(q);}//元素p所在分组的标识符publicintfind(intp){while(true){if(peleAndGroup[p]){returnp;}peleAndGroup[p];}}//把p元素所在分组和q元素所在分组合并publicvoidunion(intp,intq){//找到p元素和q元素所在组对应的树的根结点intpRootfind(p);intqRootfind(q);//如果p和q已经在同一分组则不需要合并了if(pRootqRoot){return;}//判断proot对应的树大还是qroot对应的树大最终需要把较小的树合并到较大的树中if(sz[pRoot]sz[qRoot]){eleAndGroup[pRoot]qRoot;sz[qRoot]sz[pRoot];}else{eleAndGroup[qRoot]pRoot;sz[pRoot]sz[qRoot];}//组的数量-1this.count--;}}案例 2 : 畅通工程需求:某省调查城镇交通状况得到现有城镇道路统计表表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通但不一定有直接的道路相连只要互相间接通过道路可达即可。问最少还需要建设多少条道路在我们的测试数据文件夹中有一个trffic_project.txt文件它就是诚征道路统计表下面是对数据的解释总共有20个城市目前已经修改好了7条道路问还需要修建多少条道路才能让这20个城市之间全部相通解题思路创建一个并查集UF_Tree_Weighted(20);分别调用union(0,1),union(6,9),union(3,8),union(5,11),union(2,12),union(6,10),union(4,8)表示已经修建好的道路把对应的城市连接起来如果城市全部连接起来那么并查集中剩余的分组数目为1所有的城市都在一个树中所以只需要获取当前并查集中剩余的数目减去1就是还需要修建的道路数目代码packagemain.java.Algorithms.tree;importjava.io.BufferedReader;importjava.io.InputStreamReader;publicclassTraffic_Project_Test{publicstaticvoidmain(String[]args)throwsException{//构建一个缓冲读取流BufferedReaderBufferedReaderbrnewBufferedReader(newInputStreamReader(Traffic_Project_Test.class.getClassLoader().getResourceAsStream(traffic_project.txt)));//读取第一行数据20inttotalNumberInteger.parseInt(br.readLine());//构建一个并查集对象main.java.Algorithms.tree.UF_Tree_Weighted ufnewmain.java.Algorithms.tree.UF_Tree_Weighted(totalNumber);//读取第二行数据7introadNumberInteger.parseInt(br.readLine());//循环读取7条道路for(inti1;iroadNumber;i){Stringlinebr.readLine();//0 1String[]strline.split( );intpInteger.parseInt(str[0]);intqInteger.parseInt(str[1]);//调用并查集对象的union方法让两个城市相通uf.union(p,q);}//获取当前并查集中分组的数量-1就可以得到还需要修建的道路的数目introadsuf.count()-1;System.out.println(还需要修建roads条道路才能实现畅通工程);}}