并查集的優(yōu)化

在上一節(jié)了解到并查集的快速查詢，合并，判斷歸屬組等操作，雖然這些操作都非常方便，但是在數(shù)據(jù)量較大的情況下，并查集的效率并不算高：

上一節(jié)中實現(xiàn)代碼中使用的合并方法(merge，API設計中為union)，每次合并都需要遍歷全部元素的次數(shù)，而最少要合并N-1次才能將所有元素合并到同一組，因此我們要對其合并進行優(yōu)化

為了提升union算法的性能,我們需要重新設計find方法和merge方法的實現(xiàn),此時我們先需要對我們的之前數(shù)據(jù)結(jié)構(gòu)中的groups數(shù)組的含義進行重新設定。

使用

優(yōu)化查詢分組which_group方法

我們?nèi)匀蛔実roups數(shù)組的索引作為結(jié)點的元素

groups[i]的值不再是當前結(jié)點所在的分組標識，而是當前結(jié)點的父結(jié)點，根據(jù)當前結(jié)點的父結(jié)點可以找到祖父結(jié)點，一直往上找，直到找到它的根結(jié)點，根結(jié)點則是其真正的分組

Python代碼實現(xiàn)及測試

class UF_Tree:def __init__(self, n):self.num_groups = nself.groups = [i for i in range(n)]def count_groups(self):return self.num_groupsdef in_the_same_group(self, item1, item2):return self.which_group(item1) == self.which_group(item2)def which_group(self, item):"""Find item's root------>groups[groups[groups[...groups[item]...]]]"""while self.groups[item] != item:item = self.groups[item]return itemdef merge(self, item1, item2):if self.in_the_same_group(item1, item2):returnself.groups[self.which_group(item1)] = self.groups[self.which_group(item2)]self.num_groups -= 1if __name__ == '__main__':UF = UF_Tree(5)print(f"The initial number of groups is {UF.num_groups}")print(f"The initial number of groups is {UF.groups}")while True:p = int(input(f'Input the to-be-merge element: '))q = int(input(f"Merge to the target element's group: "))if UF.in_the_same_group(p, q):print(f"They are already in the same group")continueUF.merge(p, q)print(f"The number of groups now is {UF.count_groups()}")print(UF.groups)

運行結(jié)果

The initial number of groups is 5 The initial number of groups is [0, 1, 2, 3, 4] Input the to-be-merge element: 0 Merge to the target element's group: 1 The number of groups now is 4 [1, 1, 2, 3, 4] Input the to-be-merge element: 1 Merge to the target element's group: 2 The number of groups now is 3 [1, 2, 2, 3, 4] Input the to-be-merge element: 2 Merge to the target element's group: 3 The number of groups now is 2 [1, 2, 3, 3, 4] Input the to-be-merge element: 3 Merge to the target element's group: 4 The number of groups now is 1 [1, 2, 3, 4, 4] Input the to-be-merge element:

可以尋找到item = 0的源分組為4

總結(jié)

以上是生活随笔為你收集整理的数据结构之并查集：UF-Tree优化并查集——19的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。