Система непересекающихся множеств
Описание
Система непересекающихся множеств (disjoint set) (также называемая структурой данных поиска объединения (пересечения) (union-find data structure) или множеством поиска слияния (merge-find set)) - это структура данных, которая содержит множество элементов, разделенных на определенное количество непересекающихся подмножеств. Она обеспечивает почти константное время выполнения операций (ограниченное обратной функцией Аккермана) добавления новых множеств, объединения существующих множеств и определения принадлежности элементов к одному множеству. Среди прочего, СНМ играет ключевую роль в алгоритме Краскала для построения минимального остовного дерева взвешенного связного неориентированного графа.
Основные операции СНМ:
MakeSet(x)- создает одноэлементное множество{x}Find(x)- возвращает идентификатор множества (выделенный или репрезентативный элемент), содержащего элементxUnion(x, y)- объединяет множества, содержащиеxиy
8 непересекающихся множеств, созданных с помощью MakeSet
Группировка множеств с помощью Union
Реализация
Начнем с реализации конструктора выделенного элемента множества:
// data-structures/disjoin-set/item.js
export default class Item {
constructor(value, keyCb) {
// Значение
this.value = value
// Кастомная функция извлечения ключа
this.keyCb = keyCb
// Родительский узел
this.parent = null
// Дочерние узлы
this.children = {}
}
}
Методы получения значения узла, корневого узла и определения того, является ли узел корневым:
// Возвращает ключ (значение)
getKey() {
if (this.keyCb) {
return this.keyCb(this.value)
}
return this.value
}
// Возвращает корневой узел
getRoot() {
return this.isRoot() ? this : this.parent.getRoot()
}
// Определяет, является ли узел корневым
isRoot() {
return this.parent === null
}
Методы получения ранга и потомков узла:
// Возвращает ранг (вес) узла
getRank() {
const children = this.getChildren()
if (children.length === 0) {
return 0
}
let rank = 0
for (const child of children) {
rank += 1
rank += child.getRank()
}
return rank
}
// Возвращает потомков
getChildren() {
return Object.values(this.children)
}
Методы установки родительского и добавления дочернего узла:
// Устанавливает предка
setParent(parent, forceSettingParentChild = true) {
this.parent = parent
if (forceSettingParentChild) {
parent.addChild(this)
}
return this
}
// Добавляет потомка
addChild(child) {
this.children[child.getKey()] = child
child.setParent(this, false)
return this
}
Полный код узла
Приступаем к реализации СНМ:
// data-structures/disjoin-set/index.js
import Item from './item'
export default class DisjointSet {
constructor(cb) {
// Кастомная функция извлечения ключа (значения) узла
this.cb = cb
// Непересекающиеся подмножества
this.items = {}
}
}
Метод создания подмножества:
// Создает подмножество
makeSet(value) {
// Создаем выделенный элемент
const item = new Item(value, this.cb)
// Добавляем подмножество в список
if (!this.items[item.getKey()]) {
this.items[item.getKey()] = item
}
return this
}
Метод поиска выделенного элемента:
// Ищет выделенный элемент
find(value) {
const temp = new Item(value, this.cb)
const item = this.items[temp.getKey()]
return item ? item.getRoot().getKey() : null
}
Метод объединения двух подмножеств:
// Объединяет подмножества
union(value1, value2) {
const root1 = this.find(value1)
const root2 = this.find(value2)
if (!root1 || !root2) {
throw new Error('Одно или оба значения отсутствуют!')
}
if (root1 === root2) {
return this
}
const item1 = this.items[root1]
const item2 = this.items[root2]
// Определяем, какое подмножество имеет больший ранг.
// Подмножество с меньшим рангом становится потомком подмножества с большим рангом
if (item1.getRank() < item2.getRank()) {
item2.addChild(item1)
return this
}
item1.addChild(item2)
return this
}
Метод определения принадлежности двух элементов к одному множеству:
// Определяет, принадлежат ли значения к одному множеству
isSameSet(value1, value2) {
const root1 = this.find(value1)
const root2 = this.find(value2)
if (!root1 || !root2) {
throw new Error('Одно или оба значения отсутствуют!')
}
return root1 === root2
}
Полный код СНМ
Автономную СНМ (без дополнительных зависимостей) можно реализовать следующим образом:
export default class DisjointSetAdHoc {
constructor(size) {
this.roots = new Array(size).fill(0).map((_, i) => i)
this.heights = new Array(size).fill(1)
}
find(a) {
if (this.roots[a] === a) return a
this.roots[a] = this.find(this.roots[a])
return this.roots[a]
}
union(a, b) {
const rootA = this.find(a)
const rootB = this.find(b)
if (rootA === rootB) return
if (this.heights[rootA] < this.heights[rootB]) {
this.roots[rootA] = rootB
} else if (this.heights[rootA] > this.heights[rootB]) {
this.roots[rootB] = rootA
} else {
this.roots[rootB] = rootA
this.heights[rootA]++
}
}
connected(a, b) {
return this.find(a) === this.find(b)
}
}
Тесты для выделенного элемента
Запускаем тесты:
npm run test ./data-structures/disjoint-set/__tests__/item
Тесты для СНМ
Запускаем тесты:
npm run test ./data-structures/disjoint-set/__tests__/disjoint-set
Тесты для автономной СНМ
Запускаем тесты:
npm run test ./data-structures/disjoint-set/__tests__/ad-hoc
