СНМ (наивные реализации) — различия между версиями
Free0u (обсуждение | вклад) (→Определение) |
(→Другие реализации) |
||
Строка 107: | Строка 107: | ||
== Другие реализации == | == Другие реализации == | ||
− | * [[СНМ(списки с весовой эвристикой)]] | + | * [[СНМ (списки с весовой эвристикой)]] |
− | * [[СНМ(реализация с помощью леса корневых деревьев)]] | + | * [[СНМ (реализация с помощью леса корневых деревьев)]] |
== Источники == | == Источники == |
Версия 18:02, 6 июня 2012
Содержание
Определение
Определение: |
Система непересекающихся множеств (disjoint set union, DSU) — структура данных, поддерживающая операции union(x, y) и find(k). Операция union(x, y) объединяет множества, содержащие x и y, а find(k) — выполняет поиск множества, которому принадлежит элемент k. |
Реализации
С помощью массива
Оценка работы:
init | find | union |
Пусть в массиве s хранятся номера множеств, в s[i] будет храниться номер множества, к которому принадлежит i. Этот номер отождествляет множество, find возвращает именно его. Тогда find, очевидно, будет работать за
.Чтобы объединить множества x и y, надо изменить все s[i], равные номеру множества x, на номер y. Тогда union работает за
.Псевдокод:
int s[n] init(): for i = 0 to n - 1: s[i] = i // сначала каждый элемент лежит в своем множестве find(k): return s[k] union(x, y): if s[x] == s[y]: return else: t = s[y] for i = 0 to n - 1: if s[i] == t: s[i] = s[x]
С помощью списка
Оценка работы:
init | find | union |
Будем хранить множество в виде списка. Вначале создается n списков, в которых каждый элемент является представителем своего множества. Для каждого элемента списка будем хранить ссылку на следующий элемент (next) и ссылку на голову (head). Причем ссылка на head будет корректна только у элемента-представителя. Тогда для объединения множеств достаточно перекинуть ссылку next у представителя одного множества на начало другого множества и скорректировать head у представителя другого множества. Таким образом, union работает за
.Для того, чтобы найти элемент в одном из множеств, надо идти по ссылкам next, пока он не указывает на null — тогда мы нашли элемент-представитель. Таким образом, find работает за
.Псевдокод:
s[n] init(): for i = 0 to n - 1: s[i].set = i s[i].next = null s[i].head = s[i] find(x): // подразумевается, что x — ссылка на один из элементов while x.next != null: x = x.next return x.set union(x, y): // здесь важно, что x и y — представители множеств if x == y: return else: x.next = y.head // соединили списки y.head = x.head // сделали корректную ссылку на голову для представителя нового списка
Пример работы:
Два списка до операции union:
Два списка после операции union:
Другие реализации
Источники
- Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.