scipy.cluster.hierarchy.
DisjointSet#
- class scipy.cluster.hierarchy.DisjointSet(elements=None)[source]#
用于增量连接性查询的不相交集数据结构。
在版本 1.6.0 中添加。
- 属性:
- n_subsetsint
子集的数量。
方法
add
(x)将元素 x 添加到不相交集
merge
(x, y)合并 x 和 y 的子集。
connected
(x, y)测试 x 和 y 是否在同一子集中。
subset
(x)获取包含 x 的子集。
subset_size
(x)获取包含 x 的子集的大小。
subsets
()获取不相交集中的所有子集。
__getitem__
(x)查找 x 的根元素。
注释
此类实现不相交集 [1],也称为 union-find 或 merge-find 数据结构。 find 操作(在
__getitem__
中实现)实现 路径折半 变体。 merge 方法实现 按大小合并 变体。参考
例子
>>> from scipy.cluster.hierarchy import DisjointSet
初始化不相交集
>>> disjoint_set = DisjointSet([1, 2, 3, 'a', 'b'])
合并一些子集
>>> disjoint_set.merge(1, 2) True >>> disjoint_set.merge(3, 'a') True >>> disjoint_set.merge('a', 'b') True >>> disjoint_set.merge('b', 'b') False
查找根元素
>>> disjoint_set[2] 1 >>> disjoint_set['b'] 3
测试连接性
>>> disjoint_set.connected(1, 2) True >>> disjoint_set.connected(1, 'b') False
列出不相交集中的元素
>>> list(disjoint_set) [1, 2, 3, 'a', 'b']
获取包含 'a' 的子集
>>> disjoint_set.subset('a') {'a', 3, 'b'}
获取包含 'a' 的子集的大小(无需实际实例化子集)
>>> disjoint_set.subset_size('a') 3
获取不相交集中的所有子集
>>> disjoint_set.subsets() [{1, 2}, {'a', 3, 'b'}]