当前位置：首页 > ai >正文

5.5.2_2并查集的进一步优化

ai 2025/6/16 10:29:58

知识汇总：

Find操作优化：

find操作主要是通过S[]数组一路向北来找给定节点的根节点，从给定节点到找到根节点所经过的节点路径称为查找路径。压缩路径就是让查找路径变短。

压缩路径过程：如开始让L节点找根节点A，那么会根据Find操作一路向北依次找到E、B、A，即LEBA为查找路径，压缩路径就是先找到根节点A，再将查找路径上的所有节点都挂到根节点下，即找到了根节点是A，查找路径上的节点为LEB都挂到根节点下，即index(A)=0，index(L)=11，index(E)=4,index(B)=1让S[11]=index(A)=0,S[4]=index(A)=0,S[1]=index(A)=0(开始B的S值就是0不用改)，则此时L再想找根节点直接查找1次就直达根节点A了

代码实现：

根据给定节点x数组下标先while循环通过S[]>=0找到根节点root，再while循环对找根节点过程中的节点的S值=root数组下标即挂到根节点下边，即给定节点->根节点的路径已经变成了1即压缩了路径，等下一次再找给定节点的根节点时就还可使用已经压缩好的路径查找，提高了效率，时间复杂度能大概提高到O(1)(咋还找，这是用了缓存吗，给定节点的路径压缩完路径后能一直保持不变？？？）

优化：

Find操作-----》压缩路径，使得构造树的高度不超过O(α(n)) 近似于O(1)，union操作------》小树合并大树，使得构造树的高度不超过O(log2n)，O(α(n))<< O(log2n)压缩路径很优秀，旨在目的都为降低树的高度

优化汇总：

union操作优化前：find操作查找根节点最坏情况为树为单支h较高情况，最坏时间复杂度为O(n)即要从底部查到第一个节点，在进行n个独立元素的union操作时需要unin的次数为n-1次(如2个元素union，则需要1次union操作)，且要先find再union，而find的时间复杂度是O(n)，则union操作时间复杂度为O(n²)即n*O(n)

union操作优化后(小树合并大树)：union操作优化小树合并大树后，会让树的高度不超过log2n，则find操作的时间复杂度不超过O(log2n)，在进行n个独立元素的union操作时需要n-1次union，且进行union操作时先find再union,而find的时间复杂度是O(log2n)，则union操作时间复杂度为O(nlog2n)

Find操作优化后(压缩路径)：find操作压缩路径后会让树的高度不超过O(α(n))，则find操作的时间复杂度是O(α(n))，在进行n个独立元素的union操作时需要n-1次union，且进行union操作时先find再union,而find的时间复杂度是O(α(n))，则union操作时间复杂度为O(α(n))[即(n-1)*O(α(n))=O(nα(n))]