并查集的介紹

• 并查集（Union-find）數據結構也稱作合并查找集（Merge-find set）或者不相交集數據結構（disjoint-set data structure），它是一種記錄了由一個或多個元素組成的不連續的分組的集合。并查集提供常數量的復雜度來添加、合并以及確定兩個元素是否屬于同一個集合。
• 并查集除了能夠實現這些快速便利的操作，它在Krukal算法中尋找最小生成樹的圖也起著關鍵的作用
  
  并查集結構
  并查集是一種樹形數據結構，但是它和二叉樹、紅黑樹、B樹不同，它對樹形結構的要求十分簡單：
• 同一個數據組中的元素對應在同一顆樹（判斷兩個元素是否在同一顆樹時，可以判斷根結點是否相同）
• 同一數據組中的每一個元素對應樹中的一個結點
• 不同數據組之間不存在任何相關的聯系，可以看做多個數據組成一個森林（合并數據組時，只需要將一棵樹的根結點指向另一顆樹的根結點即可）
• 樹中的結點不存在硬性的順序/父子關系

并查集的功能實現

方法設計

self.groups 是一個列表，其索引代表傳入的元素的值，其元素代表傳入元素所在分組

count_groups() 返回并查集中組的數量

which_group(item) 判斷傳入的元素item屬于哪一個群組

in_the_same_group(item1, item2) 判斷傳入的兩個元素是否在同一個分組

merge(item1, item2) 將兩個元素各自所在的分組合并到一個組，合并后的分組為后者所在的組

Python代碼實現

class UnionFind:def __init__(self, n):self.num_groups = nself.groups = [i for i in range(n)] # Let the indices be the elements, and the elements be the group numbersdef count_groups(self):return self.num_groupsdef which_group(self, item):"""The indices are items, the elements are group numbers"""return self.groups[item]def in_the_same_group(self, item1, item2):return self.which_group(item1) == self.which_group(item2)def merge(self, item1, item2):group1 = self.which_group(item1)group2 = self.which_group(item2)if group1 == group2:returnfor i in range(len(self.groups)):if self.groups[i] == group1:self.groups[i] = group2self.num_groups -= 1

代碼測試

if __name__ == '__main__':UF = UnionFind(5)print(f"The initial number of groups is {UF.num_groups}")print(f"The initial 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)

測試結果

The initial number of groups is 5 The initial 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 [2, 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 [3, 3, 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 [4, 4, 4, 4, 4] Input the to-be-merge element:

最少需要n-1 = 4 次合并，就可以將所有元素都合并到一個分組到一個組。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的数据结构之并查集：并查集的介绍与Python代码实现——18的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。