另外一个集合(或者说不属于这个集合)

一个集合里有好多元素把同类型的元素构造成一棵树其他类元素构造成另外一棵树这个元素属于哪个集合就用这棵树的根节点表示讨论哪个元素属于哪个集合就是找这个元素所在树的根节点。

森林是由多个互不相交的树构成的

1.判断某个元素属于哪个集合------》从该元素出发一路向北查到该元素所在根节点根节点是哪个就是哪个树哪个集合

2.判断2个元素是否从属相同集合---》各个元素一路向北查到各元素所在根节点就是各元素所在哪个树哪个集合再判断2个根节点是否相等相等即为在同一个集合不相等即为在不同集合

3.合并子集操作。

即把2个集合合并成一个集合可以把一个子集放到另外一个子集里成为另外一个子集的子集。

即把一棵树放到另外一棵树里成为另外一棵树的孩子。

如例子喜欢紫葡萄、绿葡萄的人各自为一个子集则可把2个子集合并成一个都喜欢葡萄的集合即可让喜欢紫葡萄的树归属到喜欢绿葡萄树的子树即可

为什么用树的双亲表示法表示并查集用孩子节点字段中的parent指针指向该节点的父节点所在的数组下标查询父节点快查找孩子节点慢(因为要遍历所有的节点找parent是该节点的)而并查集的查是一路向北找父节点的所以用双亲表示法更容易找父节点并且并查集的并是把一棵树A合并到另外一棵树B下成为树B的子树如果用双亲表示法直接把A的根节点的parent字段改成B的根节点就可完成合并综上用双亲表示法表示并查集很方便。

就是长度为n的int型数组S。

和树的双亲表示法类似即假如所有元素个数为n则定义一个长度为n的int型数组S把元素依次放在数组中每个元素对应一个下标数组中的值即为父节点的数组下标即实际数组存储的是该元素父节点的索引下标注意的是该数组S存储的是所有元素的父节点的数组下标即使有的节点元素不属于同一集合没有父节点的数组值为-1如最后一张图三个树三个集合统一放到S数组里根节点ACD在数组中的值为-1如果要把C合并到A则直接修改C对应的数组值为为A节点的下标即可即从-1修改为0就完成了并查集的合并并查集的查找即查找父节点直接查找S中的值可根据下标直接定位到父节点元素

代码实现

并查集的初始化操作初始化S[]数组中的值都为-1。

并查集就是用一个Int型的数组进行表示即UFSets开始并不知道这些元素是否属于一个集合所以把每个元素都初始化为一个个单独的子集即一个元素一个集合完成这个操作只需要把数组上的每个元素的值设为-1即可即表示每个元素都是单独的子集。

然后开始进行并查操作应该属于同一个集合的元素就合并成一个集合。

即找某个元素的所在树的根节点。

Find中x指的是元素所在数组中的下标(注意不是S[]数组中的值S[]数组中的值是元素下标的父节点下标值)目前看数组S好像就是存的是元素的父节点数组下标数组中没其他字段内容。

如要查L元素即下标为11即x11的属于哪个集合一路向北查到根节点S[11]40,即下一轮while循环X4S[4]1

0下一轮while循环X1,S[1]00,下一轮while循环X0S[0]-10退出while循环返回X0依次为查找L的父节点为EE的父节点BB的父节点AA没有父节点结束。

即L属于A节点所在集合。

即将2个不想交的集合合并成一个修改其中一个集合中的父节点为另外一个节点的下标。

要传入2个集合(2个树)的根节点下标如合并AC集合要传入A数组下标0C数组下标2即Root10Root22即把Root2合并到Root1即合并C到A先判断Root1Root2直接返回即2个相同集合的不用合并再把S[Root2]Root1即S[2]0即把要变成子树的根节点S[]中的值变成另外一个树的根节点数组下标即修改Root2的父节点数组索引下标由-1改为0

如果在合并的时候给的Root1和Root2节点并不是集合的根节点那么先通过Find操作找到这俩节点的根节点再进行Union操作

时间复杂度分析

Find操作要根据树的形态确定时间复杂度如果是最坏单支情况可能需要进行n次while循环即O(n)好的情况可能只需找一层或不用找吧即O(1)即让树的高度h变低有助于减少时间复杂度

让树的时间复杂度变小即让树的高度h变小则在合并时让小树合大树。

因为小树合大树只是让小树的父节点变成大树的大树的高度h不会改变(大树一般会比小树高合到大树之后小树只是作为一个子树出现一般应该不会影响大树的高度)如果让大树合到小树上大树的高度h一般小树高度h合过去之后大树作为子树出现则起码大树高度h还高一层且大树节点数小树节点数则大树节点在进行Find操作时都要再至少加一层高度

具体优化

如果是各个集合的根节点优化前根节点在S[]中的值为-1优化后让S[]中的值0但是S[]代表的值为整个树的节点个数比如A集合即A树有6个节点A的index0优化前S[0]-1优化后S[0]-6同理C集合S[2]-1变成S[2]-2小树合大树即C合到A(因为C有2个节点A有6个节点A是大树)合并之后A中多了2个节点即A共有8个节点S[0]-8,C不再是根节点变成S[2]S[0]

优化代码实现如下

1.用根节点的绝对值表示树的节点总数2.union操作小树合并大树

过程目前认为传入的2个节点都是根节点如果不是先去做find操作。

判断Root1和Root2是否相等即是否是相同集合相同集合不做操作直接return。

如果S[Root2]S[Root1]则Root2合并到Root1(2个S值都为负数的情况下证明root1的节点数更多)Root1是大树Root2是小树让S[Root1]S[Root2]S[Root2]Root1即Root1总节点数增加Root2父节点改变成Root1相反同上个过程

优化之后结果Find操作时间复杂度变成O(log2n),union操作时间复杂度不变还是O(1)合并后构造的树的高度不超过log2n向下取整1

知识回顾