scipy.cluster.hierarchy.

DisjointSet#

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

用于增量连通性查询的不相交集数据结构。

Added in version 1.6.0.

属性:
n_subsets整数

子集的数量。

方法

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'}]
On this page