查找邮箱注册过的网站,福建省建设厅网站节能办,上海私人做网站,做网站和商城有什么好处并查集是一种树型的数据结构#xff0c;并查集可以高校地进行如下操作#xff1a; *查询元素p和元素q是否在同一组 *合并元素p和元素q所在的组
一.并查集结构
并查集也是一种树型结构#xff0c;这种树的要求比较简单#xff1a;1.每个元素都唯一的对应一个结点#xff…并查集是一种树型的数据结构并查集可以高校地进行如下操作 *查询元素p和元素q是否在同一组 *合并元素p和元素q所在的组
一.并查集结构
并查集也是一种树型结构这种树的要求比较简单1.每个元素都唯一的对应一个结点 2.每一组数据中的多个元素都在同一颗树中 3.一个组中的数据对应的树和另外一个组中的数据对应的树之间没有任何联系 4.元素在树中并没有子符级关系的硬性要求。
简单说就是同一组的元素可以看成是一棵树。 二.并查集API设计 三.并查集的实现
1.UFint N构造方法实现
【1】初始情况下每个元素都在独立的分组中所以初始情况下并查集中的数据默认分为N个组 【2】初始化数组eleAndGroup 【3】将eleAndGroup数组的索引看做是每个结点存储的元素把eleAndGroup数组每个索引的值看做是该结点所在的分组那么初始化情况下i索引处存储的值就是i 2.union(int p,int q)合并方法实现
1.如果p和q已经在同一个分组中则无需合并 2.如果p和q不在同一个分组中则只需要将p元素所在的所有元素的组标识符修改为q元素所在组的标识符即可 3.分组数量-1
四.优化union算法--UF_Tree
1.UF_Tree算法优化
为了提升union算法的性能我们需要重新设计find方法和union方法的视线此时我们现需要对我们的之前数据结构中的eleAndGourp数组的含义进行重新设定 1.我们仍然让eleAndGroup数组的索引作为某个结点的元素 2.eleAndGroup[i]的值不再是当前结点所在的分组标识而是该结点的父结点 2.API设计 3.find(int p)查询方法实现
【1】判断当前元素p的父节点eleAndGroup[p]是不是自己如果是自己则证明已经是根结点了 【2】如果当前元素p的父结点不是自己则让peleAndGroup[p]继续找父结点的父节点知道找到根结点为止 4.union(int p,int q)合并方法实现
1.找到p元素所在树的根结点 2.找到q元素所在树的根结点 3.如果p和q已经在同一个树中则无需合并 4.如果p和q不在同一分组中则需要将p元素所在树根结点的父节点设置为q元素的根结点即可 5.分组数量减一
五.路径压缩--UF_Tree_Weighted
UF_Tree中最坏情况下union算法的时间复杂度为ON^2,其最主要的问题在于最坏情况下树的深度和数组的大小一样如果我们能够通过一些算法让合并时生成的树的深度尽可能的小就可以优化find方法。 之前我们在union算法中合并树的时候将任意的一颗树连接到另外一颗树这种方法是比较暴力的如果我们把并查集中每一棵树的大小记录下来然后再每次合并树的时候把较小的树连接到较大的树上就可以减小树的深度。
只要我们保证每次合并都能把小树合并到大树上就能够压缩合并后新树的路径这样就能提高find方法的效率。为了完成这个需求我们需要另外一个数组来记录存储每个根结点对应的树中元素的个数并且需要一些代码调整数组中的值。
UF_Tree_Weighted API设计
