DisjointSet#
- класс scipy.cluster.hierarchy.DisjointSet(элементы=None)[источник]#
Структура данных непересекающихся множеств для инкрементальных запросов на связность.
Добавлено в версии 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 структура данных. The найти операция (реализована в
__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'}]