scipy.cluster.hierarchy.

DisjointSet

class scipy.cluster.hierarchy.DisjointSet(elements=None)

用於遞增連通性查詢的 Disjoint Set 資料結構。

在版本 1.6.0 中新增。

說明

此類別實作了 disjoint set [1]，也稱為 union-find 或 merge-find 資料結構。find 操作（在 __getitem__ 中實作）實作了路徑半徑變體。merge 方法實作了依大小合併變體。

參考文獻

[1]

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

範例

在您的瀏覽器中試試看！

>>> from scipy.cluster.hierarchy import DisjointSet

初始化一個 disjoint set

>>> 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

列出 disjoint set 中的元素

>>> 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 中的所有子集

>>> disjoint_set.subsets()
[{1, 2}, {'a', 3, 'b'}]

返回在新分頁中開啟

屬性:

n_subsetsint

子集的數量。

方法

add(x)	將元素 x 新增至 disjoint set
merge(x, y)	合併 x 和 y 的子集。
connected(x, y)	測試 x 和 y 是否在同一個子集中。
subset(x)	取得包含 x 的子集。
subset_size(x)	取得包含 x 的子集的大小。
subsets()	取得 disjoint set 中的所有子集。
__getitem__(x)	尋找 x 的根元素。