Преглед на кода на Структура от данни за непресичащи се множества

{{обработка|проверка на превода}}
'''Структура от данни за непресичащи се множества''' ({{lang|en|Disjoint-set data structure, union–find data structure или merge–find set}}) в [[информатика]]та е [[структура от данни]], която съдържа колекция от непресичащи се динамични [[множество|множества]], разделени на няколко несвързани (непрепокриващи се) подмножества. Всяко множество има представител, който идентифицира множеството.

Съществуват три основни операции, които тази структура поддържа:

* '''Find:''' Определя кой елемент се съдържа в дадено подмножество.

* '''Union:''' Обединява две подмножества в едно.

* '''MakeSet:''' Образува множество, което съдържа само един елемент.

С тези три операции, много проблеми могат да бъдат решени като се разделят на отделни части.

== Непресичащи се множества в свързани списъци (''Disjoint-set linked lists'') ==
[[Файл:Disjoint-sets As Linked-lists.png|мини|250px|Представяне на множества '''{c, h, e, b}''' и '''{f, g, d}''' в свързани списъци.]]
[[Файл:Linked-list Representation.png|мини|250px|Представяне чрез свързан списък на множествата '''{c, h, e, b}''' и '''{f, g, d}''' след операция '''Union'''.]]
Един от начините за представяне на непресичащи се множества е чрез създаването на [[Списък (абстрактен тип данни)|свързан списък]] за всяко множество. Първият елемент на всеки списък служи за представител на множеството.

'''MakeSet''' създава списък от един елемент. '''Union''' обединява двата списъка. При него времето за изпълнение е константно. Недостатъкът на това приложение е, че '''Find''' изисква Big-O notation (''n'') или линейно време, за да премине от даден елемент до началото на списъка.

Това може да бъде избегнато чрез поставянето на указател във всеки възел на свързания списък, който да сочи към началото на списъка. Докато този указател е свързан с представителя на множеството, '''Find''' се изпълнява за константно време. При този вариант, когато се добавят елементи с '''Union''', всеки добавен елемент трябва да сочи към началото на новия сформиран списък. Извършването на тази операция, в този случай изисква време за изпълнение Big-O notation (''n'').

Ако се знае дължината на всеки списък, времето за изпълнение може да бъде оптимизирано. Това може да се постигне като винаги по-малкият списък се добавя към по-големия. Използвайки този похват, наричан още weighted-union, поредица от <math>m</math> на брой '''MakeSet''', '''Union''' и '''Find''' операции върху <math>n</math> на брой елементи се извършват за <math>O(m + n log n)</math> време за изпълнение. За да се оптимизира времето за изпълнение е нужна друга структура от данни.

=== Анализ на подхода ===
Нека предположим, че имаме колекция от списъци и всеки възел от всеки списък съдържа обект (името на списъка, към който принадлежи и броя на елементи в него). Също така, нека предположим, че сумата на броя елементи във всички списъци е <math>n</math> (т.е. броят на всички елементи е <math>n</math>). Искаме да можем да съединим всеки два от тези списъци и при това да обновим всеки техен възел, така че все още да съдържа името на списъка, към който принадлежи. Правилото за сливане на списъци <math>A</math> и <math>B</math> е, че ако <math>A</math> е по-голямо от <math>B</math>, тогава сливаме елементите от <math>B</math> в <math>A</math> и обновяваме елементите, които са били в <math>B</math>.

Избираме случаен елемент от списъка <math>L</math>, да кажем <math>x</math>. Искаме да преброим колко пъти в най-лошия случай ще трябва да обновим <math>x</math>, за да съдържа името на списъка, към който принадлежи. Елементът <math>x</math> ще съдържа името само, когато списъкът, към който принадлежи се обедини със списък със същия размер или по-голям. Всеки път, когато това се случи, размерът на списъка, към който принадлежи <math>x</math> се увеличава най-малко два пъти. Въпросът е колко пъти може да се увеличи преди да стане с размер на <math>n</math> (след това списъкът, съдържащ <math>x</math> ще съдържа всички <math>n</math> елементи)?
Отговорът е точно <math>\log_2(n)</math>. Всеки даден елемент от всеки даден списък в описаната структура ще трябва да се обнови <math>\log_2(n)</math> пъти в най-лошия случай. Затова обновяването на списък от <math>n</math> елементи, подредени по този начин отнема <math>O(n \log(n))</math> време в най-лошия случай. '''Find''' операцията може да бъде с време за изпълнение <math>O(1)</math> за тази структура, защото всеки възел съдържа името на списъка, към който принадлежи.

Подобен е и случаят със съединяването на [[Дърво (структура от данни)|дървета]].

== Непресичащи се множества в гора от дървета (''Disjoint-set forests (DSF)'') ==
За по-бързо обработване на непресичащи се множества, множествата се представят чрез дървета, като всеки възел съдържа един член на множеството, а дървото представя цялото множество.

Непресичащи се множества в гора са [[структура от данни]], където всяко множество се представя като [[Дърво (структура от данни)|дърво]], в което всеки връх сочи единствено към предходния елемент (родителя). Този тип дървета за пръв път се описват от [[Бернард Галер]] и [[Майкъл Фишер]] през 1964 г., въпреки че анализирането им е отнело много години.

В гората от непресичащи се множества, представителят на всяко множество е корена на дървото. '''Find''' следва родителските върхове, докато стигне до корена. '''Union''' комбинира две дървета в едно, като се прикача корена от едното към корена от другото дърво. Един от начините да се разгледа това е:

 '''function''' ''MakeSet''(x)
 x.parent := x

 '''function''' ''Find''(x)
 if x.parent == x
 return x
 else
 return ''Find''(x.parent)

 '''function''' ''Union''(x, y)
 xRoot := ''Find''(x)
 yRoot := ''Find''(y)
 xRoot.parent := yRoot

В тази си форма, този подход не е по-добър от този за свързани списъци, защото дървото, което се създава може да е силно дисбалансирано. Обаче, това може да се подобри по два начина – ''сливане по ранг'' и ''свиване на пътя''.

=== Сливане по ранг (Union by rank) ===
''Сливане по ранг'' се състои в това винаги по-малкото дърво да се прикача към корена на по-голямото. След като височината на дървото определя времето за изпълнение на операцията, подходящата оптимизация е, дървото с по-малка дълбочина да се добавя под корена на това с по-голяма дълбочина. По този начин, височината на новото дърво се увеличава само, когато събраните дървета имат еднаква дълбочина. В контекста на този алгоритъм терминът ''ранг'' е използван вместо ''дълбочина/височина'', защото рангът и дълбочината спират да бъдат равни, след като се сравнява и пътя за обхождане (описан по-долу). Дървета, състоящи се от един елемент, се дефинират с ранг, равен на нула и когато две дървета с един и същ ранг ''r'' се слеят, рангът на новото дърво е ''r + 1''. Ако се приложи тази техника се разбира, че това е най-лошият сценарий за операциите '''MakeSet''', '''Union''' или '''Find''' и времето им за изпълнение е <math>O(\log n)</math>. Псевдокод за подобрение на <code>MakeSet</code> и <code>Union</code>:
 '''function''' ''MakeSet''(x)
 x.parent := x
 x.rank := 0

 '''function''' ''Union''(x, y)
 xRoot := ''Find''(x)
 yRoot := ''Find''(y)
 if xRoot == yRoot
 return

 // x и y не са вече в същото множество, тогава се обединяват
 if xRoot.rank < yRoot.rank
 xRoot.parent := yRoot
 else if xRoot.rank > yRoot.rank
 yRoot.parent := xRoot
 else
 yRoot.parent := xRoot
 xRoot.rank := xRoot.rank + 1

=== Свиване на пътя (Path compression) ===
[[Файл:Disjoint-set-forest-path-compression.jpg|450px|мини|Свиване на пътя по време на операцията Find-Set. Дървото от ляво представя множество преди да се изпълни Find-Set(a). Триъгълниците представят поддървета. Всеки връх има указател, сочещ към неговия родител. В дясната част е изобразено множеството след изпълнение на операцията Find-Set(a). В този случай всеки връх сочи директно към корена.]]

''Свиване на пътя'' представлява опростяване на структурата на дървото, когато върху него се прилага операцията '''Find'''. Основната идея е, че всеки посетен възел по пътя до корена може да бъде прикачен директно към него. За да бъде това изпълнено, '''Find''' рекурсивно преминава през дървото и променя всяка връзка на родителя на възела да сочи към корена, който е намерил. По този начин структурата на дървото се опростява значително и се увеличава скоростта за изпълнение на операции не само върху елементите на дървото, но и към тези, рефериращи към тях.

Оптимизация на <code>Find</code>:

 '''function''' ''Find''(x)
 if x.parent != x
 x.parent := ''Find''(x.parent)
 return x.parent

Тези две техники се допълват взаимно и приложени заедно времето за изпълнение на операция е само <math>O(\alpha(n))</math>, където <math>\alpha(n)</math> е [[обратната функция]] на <math>n = f(x) = A(x,x)</math> и <math>A</math> е изключително бързо растяща [[Акерман функция]]. Щом като <math>\alpha(n)</math> е обратната функция, <math>\alpha(n)</math> е по-малко от 5 за всички отдалечени практически стойности на <math>n</math>. Въпреки всичко времето за изпълнение на операция е малка константа.

== Приложения ==
Структурите от данни за непресичащи се множества са помощен инструмент, използван при различни алгоритми. Те са ефикасни и използват малко памет. Използват се за реализиране на висока производителност и [[унификация]]. Едно от многото им приложения е за определяне броя на компонентите на свързаност на неориентиран граф и за имплементиране на алгоритъма на Крускал за намиране на минимално покриващо дърво.

=== Свързани компоненти на неориентиран граф ===
[[Файл:Connected Components.png|мини|Граф с четири свързани компонента : {a, b, c, d}, {e, f, g}, {h, i} и {j}.]]

Този модел може да се използва за определяне дали два върха принадлежат към същия компонент или добавянето на ребро между тях би довело до цикъл.

Процедурата CONNECTED-COMPONENTS (Свързани-Компоненти) следи използваните операции с несвързани множества, за да изчисли свързаността на компонентите на графа. След като CONNECTED-COMPONENTS обработи графа, процедурата SAME-COMPONENT (Еднакъв-Компонент) отговаря на заявките за това дали два върха са в същия свързан компонент. (В псевдокода множествата от върхове на граф G се обозначават с ''G.V'', а множеството от ребра с ''G.E''). Процедурата CONNECTED-COMPONENTS първоначално поставя всеки вектор ν (''vertex ν'') в своето множество. След това, за всяко ребро (u, ν) (''edge(u, ν)'') обединаява множествата, съдържащи u и ν.

 CONNECTED-COMPONENTS(G)
 '''for''' each vertex ν ∈ G.V
 MAKE-SET (ν)
 '''for''' each edge(u, ν)∈ G.E
 '''if''' FIND-SET.(u) ≠ FIND-SET(ν)
 UNION(u, ν)

 SAME-COMPONENT(u, ν)
 '''if''' FIND-SET(u) == FIND-SET(ν)
 '''return''' TRUE
 '''else return''' FALSE

Следващата таблица илюстрира как CONNECTED-COMPONENTS изчислява несвързаните множества.

 '''Обработвани ребра'''	 '''Колекция от непресичащи се множества'''
 --------------------------------------------------------------------------------------
 ''първоначални множества'' {a} {b} {c} {d} {e} {f} {g} {h} {i} {j}
 (b,d)	 {a}	 {b,d} {c} {e} {f} {g} {h}	{i} {j}
 (e,g)	 {a}	 {b,d} {c} {e,g} {f}	{h}	{i} {j}
 (a,c) 	 {a,c}	 {b,d} {e,g} {f}	{h}	{i} {j}
 (h,i) 	 {a,c} {b,d} {e,g} {f}	{h,i} {j}
 (a,b)	 {a,b,c,d}	 {e,g} {f}	{h,i} {j}
 (e,f) 	 {a,b,c,d}	 {e,f,g}	 {h,i} {j}
 (b,c) 	 {a,b,c,d}	 {e,f,g}	 {h,i} {j}

В реално изпълнение на алгоритъма за свързани компоненти, представителите на графа и структурата от данни за непресичащите се множества ще трябва да реферират помежду си. Това означава, че обект, представящ вектор, ще съдържа указател към кореспондиращия обект от несвързани множества, както и обратно.<ref name="IntroductionToAlgorithms">{{cite book |first1=Thomas H. |last1=Cormen |first2=Charles E. |last2=Leiserson |first3=Ronald L. |last3=Rivest |first4=Clifford |last4=Stein |title=Introduction to Algorithms |url=https://archive.org/details/introductiontoal00corm_453 |edition=Third |publisher=MIT Press |year=2009 |isbn=978-0-262-53305-8 |chapter=Chapter 21: Data structures for Disjoint Sets |pages=[https://archive.org/details/introductiontoal00corm_453/page/n581 561]–585 }}</ref>

=== Алгоритъм на Крускал ===
Алгоритъмът на Крускал се използва за намиране на минимално (максимално) покриващо дърво на тегловен граф.

 KRUSKAL(G):
 A = ∅
 '''foreach''' vertex ν ∈ G.V:
 MAKE-SET(ν)
 '''foreach''' (u, ν)∈ G.E ordered by weight(u, ν), increasing:
 '''if''' FIND-SET(u) ≠ FIND-SET(ν):
 A = A ∪ {(u, ν)}
 UNION(u, ν)
 '''return''' A<ref name="IntroductionToAlgorithms"/>

== История ==
Докато идеите, използвани за непресичащите се множества в гора от дървета отдавна са познати, през 1975 г. Робърт Тарджан е първия, който доказва горната граница (и частни случаи на долната граница) в условие на обратната функция на Акерман. До този момент най-доброто време за операция, доказано от Хопкрофт и Улман, е <math>O(log* n)</math>, [[итериран логаритъм|итерирания логаритъм]] от n, друга бавно растяща функция (но не чак толкова бавно като обратната функция на Акерман).

[[Робърт Тарджан]] и Van Leeuwen разработват така наречените ''one-pass Find'' алгоритми, които са по-ефективни на практика, защото се запазва същата сложност.

През 2007 г. Sylvain Conchon и Jean-Christophe Filliâtre разработват устойчива версия на структурата от данни непресичащи се множества в гора от дървета, позволяваща предишни състояния на структурата да бъдат запазени и доказват верността ѝ, използвайки асистента за доказателства [[Coq]]. Въпреки това, имплементацията е асимптотична, само ако се използва краткотрайно или ако една и съща версия на структурата се използва многократно с ограничено връщане назад.

== Източници ==
{{Reflist}}

{{Превод от|en|Disjoint-set data structure|656923864}}

[[Категория:Структури от данни]]
[[Категория:Алгоритми за търсене]]