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

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

Версия 18:21, 13 марта 2012

Определение:
Система непересекающихся множеств(disjoint set union, DSU) - структура данных, поддерживающая операции [math] union(x, y) [/math] - объединения множеств, содержащих x и y, и [math] find(k) [/math] - поиск множества, которому принадлежит элемент k.


Пример работы

Здесь будет пример работы

Реализации

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

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

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

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

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

Псевдокод:

int s[n]
init():
    for i = 0 to s.size - 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 s.size - 1:
            if s[i] == t:
                s[i] = s[x]

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

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

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

Псевдокод:

s[n]
init():
    for i = 0 to n - 1:
        s[i].set = i
        s[i].next = Null
        s[i].tail = s[i]

find(x)://подразумевается, что x - ссылка на один из элементов
    while x.next != Null:
        x = x.parent
    return x.set

union(x, y)://здесь важно, что x и y - представители множеств
    if x == y:
        return
    else:
        y.next = x.tail
        x.tail = y.tail

Два списка до операции union: 1.GIF

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

Источники

  • Т. Кормен - Алгоритмы, построение и анализ. Глава V-22.

Система непересекающихся множеств и её применения