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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (С помощью списка)
(оформление)
Строка 30: Строка 30:
  
 
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда <math> \mathrm{union} </math> работает за <tex>O(n)</tex>.
 
Чтобы объединить множества <tex> x </tex> и <tex> y </tex>, надо изменить все <tex> s[i] </tex>, равные номеру множества <tex> x </tex>, на номер <tex> y </tex>. Тогда <math> \mathrm{union} </math> работает за <tex>O(n)</tex>.
<code>
+
 
 
  '''int''' s[n]
 
  '''int''' s[n]
 
  '''func''' init():
 
  '''func''' init():
 
     '''for''' i = 0 '''to''' n - 1
 
     '''for''' i = 0 '''to''' n - 1
 
         s[i] = i              <font color=green> // сначала каждый элемент лежит в своем множестве </font>
 
         s[i] = i              <font color=green> // сначала каждый элемент лежит в своем множестве </font>
</code>
+
 
<code>
 
 
  '''int''' find(k):
 
  '''int''' find(k):
 
     '''return''' s[k]
 
     '''return''' s[k]
</code>
+
 
<code>
 
 
  '''func''' union(x, y):
 
  '''func''' union(x, y):
 
     '''if''' s[x] == s[y]
 
     '''if''' s[x] == s[y]
Строка 49: Строка 47:
 
             '''if''' s[i] == t
 
             '''if''' s[i] == t
 
                 s[i] = s[x]
 
                 s[i] = s[x]
</code>
 
  
 
=== С помощью списка ===
 
=== С помощью списка ===
Строка 68: Строка 65:
 
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.
 
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.
  
<code>
 
 
  '''struct''' SetItem  
 
  '''struct''' SetItem  
 
     '''int''' data       
 
     '''int''' data       
Строка 83: Строка 79:
 
         s[i].tail = s[i]
 
         s[i].tail = s[i]
 
         s[i].next = null
 
         s[i].next = null
</code>
+
 
<code>
 
 
  '''int''' find('''SetItem''' x):                        <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font>
 
  '''int''' find('''SetItem''' x):                        <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font>
 
     '''return''' x.head.data
 
     '''return''' x.head.data
</code>
+
 
<code>
 
 
  '''func''' union('''SetItem''' x, '''SetItem''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font>
 
  '''func''' union('''SetItem''' x, '''SetItem''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font>
 
     x = x.head
 
     x = x.head
Строка 99: Строка 93:
 
         y.head = x
 
         y.head = x
 
         y = y.next
 
         y = y.next
</code>
+
 
 
[[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]
 
[[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]
  

Версия 11:54, 27 сентября 2018

Система (лес, объединение) непересекающихся множеств (СНМ, disjoint set forest, DSF, disjoint set union, DSU) — иерархическая структура данных, позволяющая эффективно работать с множествами.

Описание

Структура хранит набор объектов (например, чисел от [math] 0 [/math] до [math] n - 1 [/math]) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.

Определены две операции:

  • [math] \mathrm{union(x, y)} [/math] — объединяет множества, содержащие [math] x [/math] и [math] y [/math]
  • [math] \mathrm{find (x)} [/math] — возвращает представителя множества, в котором находится [math] x [/math]

Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов [math] x [/math] и [math] y [/math] одному множеству достаточно сравнить [math] \mathrm{find (x)} [/math] и [math] \mathrm{find(y)} [/math].

Пример работы СНМ

Реализации

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

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

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

int s[n]
func init():
    for i = 0 to n - 1
        s[i] = i                // сначала каждый элемент лежит в своем множестве 
int find(k):
    return s[k]
func 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]

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

Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на [math] head [/math], который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на [math] head [/math]. Значит [math] \mathrm{find} [/math] работает за [math] O(1) [/math].

Для объединения множеств потребуется объединить два списка и обновить ссылки на [math] head [/math]. Таким образом, [math] \mathrm{union} [/math] работает за [math] O(n) [/math]. Чтобы объединить два списка, нужно хранить ссылку на [math] tail [/math]. Ее можно хранить в голове списка.

struct SetItem 
    int data       
    SetItem head
    SetItem next
    SetItem tail
SetItem s[n]
func init():
    for i = 0 to n - 1
        s[i].data = i
        s[i].head = s[i]         
        s[i].tail = s[i]
        s[i].next = null
int find(SetItem x):                         // подразумевается, что [math] x [/math] — ссылка на один из элементов 
    return x.head.data
func union(SetItem x, SetItem y):  // [math] x [/math] и [math] y [/math] — элементы множеств
    x = x.head
    y = y.head
    if x == y
        return
    x.tail.next = y                          // соединим списки 
    x.tail = y.tail                          // сделаем корректную ссылку на [math] tail [/math] в [math] head[/math]
    while y [math] \neq [/math] null                          // скорректируем ссылки на [math] head [/math] у элементов множества [math] y [/math] 
        y.head = x
        y = y.next
Пример объединения двух множеств (union)

Другие реализации

Источники информации