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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (С помощью списка)
м (rollbackEdits.php mass rollback)
 
(не показаны 54 промежуточные версии 8 участников)
Строка 1: Строка 1:
{{Определение
+
'''Система (лес, объединение) непересекающихся множеств''' (СНМ, disjoint set forest, DSF, disjoint set union, DSU) {{---}} иерархическая структура данных, позволяющая эффективно работать с множествами.
| definition =
+
__TOC__
Система непересекающихся множеств (disjoint set union, DSU) {{ --- }} структура данных, поддерживающая операции <tex>union(x, y)</tex> {{ --- }} объединения множеств, содержащих <tex>x</tex> и <tex>y</tex>, и <tex>find(k)</tex> {{ --- }} поиск множества, которому принадлежит элемент <tex>k</tex>.
+
== Описание ==
}}
+
Структура хранит набор объектов (например, чисел от <tex> 0 </tex> до <tex> n - 1 </tex>) в виде непересекающихся множеств. У каждого множества есть конкретный представитель.
 +
 
 +
Определены две операции:
 +
* <math> \mathrm{union(x, y)} </math> {{ --- }} объединяет множества, содержащие <tex> x </tex> и <tex> y </tex>
 +
* <math> \mathrm{find (x)} </math> {{ --- }} возвращает представителя множества, в котором находится <tex> x </tex>
 +
Для любого элемента множества представитель всегда одинаковый. Поэтому чтобы проверить принадлежность элементов <tex> x </tex> и <tex> y </tex> одному множеству достаточно сравнить <math> \mathrm{find (x)} </math> и <math> \mathrm{find(y)} </math>.
  
__TOC__
+
[[Файл:DSU_1_Example.png|500px|center|Пример работы СНМ]]
  
== Пример работы ==
 
Здесь будет пример работы
 
 
== Реализации ==
 
== Реализации ==
=== С помощью массива "цветов" ===
+
=== С помощью массива ===
 +
 
 +
<!--
 
'''Оценка работы:'''
 
'''Оценка работы:'''
{| border="1"
+
{| class="wikitable" border="1"
  |<tex>init</tex>
+
  |init
  |<tex>find</tex>
+
  |find
  |<tex>union</tex>
+
  |union
 
  |-
 
  |-
 
  |<tex>O(n)</tex>
 
  |<tex>O(n)</tex>
Строка 20: Строка 25:
 
  |<tex>O(n)</tex>
 
  |<tex>O(n)</tex>
 
  |}
 
  |}
Введем массив <tex>color</tex>, в <tex>color[i]</tex> будет храниться цвет множества, к которому принадлежит <tex>i</tex>. Тогда <tex>find</tex>, очевидно, будет работать за <tex>O(1)</tex>.
+
-->
 +
 
 +
Пусть в массиве s хранятся номера множеств, в <tex> s[i] </tex> будет храниться номер множества, к которому принадлежит <tex> i </tex>. Этот номер отождествляет множество, <math> \mathrm{find} </math> возвращает именно его. Тогда <math> \mathrm{find} </math>, очевидно, будет работать за <tex>O(1)</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>.
 +
 
 +
'''int''' s[n]
 +
'''func''' init():
 +
    '''for''' i = 0 '''to''' n - 1
 +
        s[i] = i              <font color=green> // сначала каждый элемент лежит в своем множестве </font>
  
Чтобы объединить множества <tex>x</tex> и <tex>y</tex>, надо изменить все <tex>color[i]</tex>, равные цвету <tex>x</tex>, на цвет <tex>y</tex>. Тогда <tex>union</tex> работает за <tex>O(n)</tex>.
+
'''int''' find(k):
 +
    '''return''' s[k]
  
'''Псевдокод:'''
+
'''func''' union(x, y):
int color[n]
+
     '''if''' s[x] == s[y]
init():
+
         '''return'''
    for i = 0 to n - 1:
+
     '''else'''
        color[i] = i //сначала каждый элемент лежит в своем множестве
+
         t = s[y]
+
         '''for''' i = 0 '''to''' n - 1
find(k):
+
             '''if''' s[i] == t
    return color[k]
+
                 s[i] = s[x]
 
union(x, y):
 
     if color[x] == color[y]:
 
         return
 
     else:
 
         t = color[y]
 
         for i = 0 to n - 1:
 
             if color[i] == t:
 
                 color[i] = color[x]
 
'''Пример работы:'''
 
бла-бла-бла
 
  
 
=== С помощью списка ===
 
=== С помощью списка ===
'''Оценка работы:'''
+
<!--'''Оценка работы:'''
{| border="1"
+
{| class="wikitable" border="1"
  |<tex>init</tex>
+
  |init
  |<tex>find</tex>
+
  |find
  |<tex>union</tex>
+
  |union
 
  |-
 
  |-
 
  |<tex>O(n)</tex>
 
  |<tex>O(n)</tex>
 
  |<tex>O(n)</tex>
 
  |<tex>O(n)</tex>
 
  |<tex>O(1)</tex>
 
  |<tex>O(1)</tex>
  |}
+
  |}-->
Пусть каждое множество хранится в виде списка. Вначале создается <tex>n</tex> списков, в котором каждый элемент является представителем своего множества. Для каждого списка будем хранить ссылку на следующий элемент <tex>(next)</tex> и ссылку на голову (<tex>head</tex>). Тогда для объединения множеств надо будет просто перекинуть ссылку <tex>next</tex> на начало другого множества. Таким образом, <tex>union</tex> работает за <tex>O(1)</tex>.
 
  
Для того, чтобы найти элемент в одном из множеств, надо идти по ссылкам <tex>next</tex>, пока он не указывает на <tex>null</tex> {{ --- }} тогда мы нашли элемент-представитель. Таким образом, <tex>find</tex> работает за <tex>O(n)</tex>.
+
Будем хранить множество в виде списка. Для каждого элемента списка храним ссылку на следующий элемент и указатель на <tex> head </tex>, который является представителем. Для того чтобы найти представителя, нужно перейти по ссылке на <tex> head </tex>. Значит <math> \mathrm{find} </math> работает за <tex> O(1) </tex>.
  
Псевдокод:
+
Для объединения множеств потребуется объединить два списка и обновить ссылки на <tex> head </tex>. Таким образом, <math> \mathrm{union} </math> работает за <tex> O(n) </tex>.
s[n]
+
Чтобы объединить два списка, нужно хранить ссылку на <tex> tail </tex>. Ее можно хранить в голове списка.
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 //сделали корректную ссылку на голову для представителя нового списка
 
  
'''Пример работы:'''
+
'''struct''' SetItem
 +
    '''int''' data     
 +
    '''SetItem''' head
 +
    '''SetItem''' next
 +
    '''SetItem''' tail
  
Два списка до операции <tex>union</tex>:
+
'''SetItem''' s[n]
  
[[Файл:DSU_1_X.png]]
+
'''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
  
[[Файл:DSU_1_Y.png]]
+
'''int''' find('''SetItem''' x):                       <font color=green> // подразумевается, что <tex> x </tex> {{ --- }} ссылка на один из элементов </font>
 +
    '''return''' x.head.data
  
Два списка после операции <tex>union</tex>:
+
'''func''' union('''SetItem''' x, '''SetItem''' y): <font color=green> // <tex> x </tex> и <tex> y </tex> {{ --- }} элементы множеств</font>
 +
    x = x.head
 +
    y = y.head
 +
    '''if''' x == y
 +
        '''return'''
 +
    x.tail.next = y                        <font color=green> // соединим списки </font>
 +
    x.tail = y.tail                        <font color=green> // сделаем корректную ссылку на <tex> tail </tex> в <tex> head</tex></font>
 +
    '''while''' y <tex> \neq </tex> null                        <font color=green> // скорректируем ссылки на <tex> head </tex> у элементов множества <tex> y </tex> </font>
 +
        y.head = x
 +
        y = y.next
  
[[Файл:DSU_1_XY.png]]
+
[[Файл:DSU_list_example.png|800px|center|Пример объединения двух множеств (union)]]
  
 
== Другие реализации ==
 
== Другие реализации ==
* [[СНМ(списки с весовой эвристикой)]]
+
* [[СНМ (списки с весовой эвристикой)]]
* [[СНМ(реализация с помощью леса корневых деревьев)]]
+
* [[СНМ (реализация с помощью леса корневых деревьев)]]
  
== Источники ==
+
== Источники информации ==
 +
*[http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D0%B5%D0%BA%D0%B0%D1%8E%D1%89%D0%B8%D1%85%D1%81%D1%8F_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2 Википедия {{---}} Система непересекающихся множеств]
 +
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]
 
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.
 
* Т. Кормен - Алгоритмы, построение и анализ. Второе издание. Часть V. Глава 21.
 
== Ссылки ==
 
* [http://habrahabr.ru/blogs/algorithm/104772/ Система непересекающихся множеств и её применения]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Структуры данных]]

Текущая версия на 19:28, 4 сентября 2022

Система (лес, объединение) непересекающихся множеств (СНМ, 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)

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

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