СНМ (наивные реализации) — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Другие реализации)
Строка 1: Строка 1:
 
__TOC__
 
__TOC__
 
 
== Определение ==
 
== Определение ==
  
<!--
+
Если у нас есть набор чисел от 0 до N - 1, то ''система непересекающихся множеств (disjoint set union, DSU)'' позволяет объединять их в множества и для каждого элемента узнавать представителя множества, к которому он относится.
{{Определение
 
| 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.
 
 
 
 
 
  
}}
+
То есть определены две операции:
 +
* union(x, y) {{ --- }} объединяет множества, содержащие x и y
 +
* find(x) {{ --- }} возвращает представителя множества, в котором находится x
  
[[Файл:DSU_1_Example.png|400px|thumb|Пример работы СНМ]]
+
[[Файл:DSU_1_Example.png|500px|left|thumb|Пример работы СНМ]]
<!--
 
 
<br clear="all" />  
 
<br clear="all" />  
-->
 
  
 
== Реализации ==
 
== Реализации ==

Версия 18:59, 10 июня 2012

Определение

Если у нас есть набор чисел от 0 до N - 1, то система непересекающихся множеств (disjoint set union, DSU) позволяет объединять их в множества и для каждого элемента узнавать представителя множества, к которому он относится.

То есть определены две операции:

  • union(x, y) — объединяет множества, содержащие x и y
  • find(x) — возвращает представителя множества, в котором находится x
Пример работы СНМ


Реализации

С помощью массива

Оценка работы:

init find union
[math]O(n)[/math] [math]O(1)[/math] [math]O(n)[/math]

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

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

Псевдокод:

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
[math]O(n)[/math] [math]O(n)[/math] [math]O(1)[/math]

Будем хранить множество в виде списка. Вначале создается n списков, в которых каждый элемент является представителем своего множества. Для каждого элемента списка будем хранить ссылку на следующий элемент (next) и ссылку на голову (head). Причем ссылка на head будет корректна только у элемента-представителя. Тогда для объединения множеств достаточно перекинуть ссылку next у представителя одного множества на начало другого множества и скорректировать head у представителя другого множества. Таким образом, union работает за [math]O(1)[/math].

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

Псевдокод:

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.

Ссылки