Просмотр исходного текста страницы СНМ (наивные реализации)

__TOC__

== Определение ==

<!--
{{Определение
| definition =
Система непересекающихся множеств (disjoint set union, DSU) {{ --- }} структура данных, поддерживающая операции union(x, y) {{ --- }} объединения множеств, содержащих x и y, и find(k) {{ --- }} поиск множества, которому принадлежит элемент k.
}}
-->
{{Определение
| definition =
Система непересекающихся множеств (disjoint set union, DSU) {{ --- }} структура данных, поддерживающая операции union(x, y) и find(k). Операция union(x, y) объединяет множества, содержащие x и y, а find(k) {{ --- }} выполняет поиск множества, которому принадлежит элемент k.



}}

[[Файл:DSU_1_Example.png|400px|thumb|Пример работы СНМ]]
<!--
<br clear="all" /> 
-->

== Реализации ==
=== С помощью массива ===
'''Оценка работы:'''
{| class="wikitable" border="1"
 |init
 |find
 |union
 |-
 |<tex>O(n)</tex>
 |<tex>O(1)</tex>
 |<tex>O(n)</tex>
 |}
<!-- Введем массив s, в s[i] будет храниться номер множества, к которому принадлежит i. Этот номер является идентификатором множества. Тогда find, очевидно, будет работать за <tex>O(1)</tex>.
-->

Пусть в массиве s хранятся номера множеств, в s[i] будет храниться номер множества, к которому принадлежит i. Этот номер отождествляет множество, find возвращает именно его. Тогда find, очевидно, будет работать за <tex>O(1)</tex>.

Чтобы объединить множества x и y, надо изменить все s[i], равные номеру множества x, на номер y. Тогда union работает за <tex>O(n)</tex>.

'''Псевдокод:'''
 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]

=== С помощью списка ===
'''Оценка работы:'''
{| class="wikitable" border="1"
 |init
 |find
 |union
 |-
 |<tex>O(n)</tex>
 |<tex>O(n)</tex>
 |<tex>O(1)</tex>
 |}
Будем хранить множество в виде списка. Вначале создается n списков, в которых каждый элемент является представителем своего множества. Для каждого элемента списка будем хранить ссылку на следующий элемент (next) и ссылку на голову (head). Причем ссылка на head будет корректна только у элемента-представителя. Тогда для объединения множеств достаточно перекинуть ссылку next у представителя одного множества на начало другого множества и скорректировать head у представителя другого множества. Таким образом, union работает за <tex>O(1)</tex>.

Для того, чтобы найти элемент в одном из множеств, надо идти по ссылкам next, пока он не указывает на null {{ --- }} тогда мы нашли элемент-представитель. Таким образом, find работает за <tex>O(n)</tex>.

'''Псевдокод:'''
 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:

[[Файл:DSU_1_X.png]]

[[Файл:DSU_1_Y.png]]

Два списка после операции union:

[[Файл:DSU_1_XY.png]]

== Другие реализации ==
* [[СНМ(списки с весовой эвристикой)]]
* [[СНМ(реализация с помощью леса корневых деревьев)]]

== Источники ==
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.

== Ссылки ==
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]

[[Категория: Дискретная математика и алгоритмы]]