scipy.cluster.hierarchy.

DisjointSet#

class scipy.cluster.hierarchy.DisjointSet(elements=None)[源代码]#

用于递增连接查询的离散集合数据结构。

从 1.6.0 版本起添加。

注释

此类实现离散集合 [1]，也称为并查集或合并查找数据结构。查找操作（在 __getitem__ 中实现）实现路径减半变体。合并方法实现按大小合并变体。

引用

[1]

示例

>>> 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'}]

属性:

方法