scipy.cluster.hierarchy.DisjointSet¶
- class scipy.cluster.hierarchy.DisjointSet(elements=None)[源代码]¶
增量连接查询的不相交集合数据结构。
1.6.0 新版功能.
注意事项
此类实现不相交的集合 [1], 也称为 union-find 或 merge-find 数据结构。这个 find 操作(在中实施 __getitem__ )实现了 路径减半 变种。这个 合并 方法实现了 按大小合并 变种。
参考文献
示例
>>> 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'}
获取不相交集中的所有子集：
>>> disjoint_set.subsets() [{1, 2}, {'a', 3, 'b'}]
- 属性
- n_subsets集成
子集的数量。
方法：
add\(X)添加元素 x 不相交集的步骤
merge\(X，y)合并以下各项的子集 x 和 y 。
connected\(X，y)测试是否 x 和 y 都在同一子集中。
subset\(X)获取包含以下内容的子集 x 。
subsets\()获取不相交集合中的所有子集。
__getitem__\(X)查找的根元素 x 。