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

Структура от данни за непресичащи се множества (на английски: Disjoint-set data structure, union–find data structure или merge–find set) в информатиката е структура от данни, която съдържа колекция от непресичащи се динамични множества, разделени на няколко несвързани (непрепокриващи се) подмножества. Всяко множество има представител, който идентифицира множеството.

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

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

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

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

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

Непресичащи се множества в свързани списъци (Disjoint-set linked lists) редактиране

Представяне на множества {c, h, e, b} и {f, g, d} в свързани списъци.

Представяне чрез свързан списък на множествата {c, h, e, b} и {f, g, d} след операция Union.

Един от начините за представяне на непресичащи се множества е чрез създаването на свързан списък за всяко множество. Първият елемент на всеки списък служи за представител на множеството.

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

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

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

Анализ на подхода редактиране

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

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

Подобен е и случаят със съединяването на дървета.

Непресичащи се множества в гора от дървета (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 и времето им за изпълнение е $O(\log n)$ . Псевдокод за подобрение на MakeSet и Union:

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) редактиране

Свиване на пътя по време на операцията Find-Set. Дървото от ляво представя множество преди да се изпълни Find-Set(a). Триъгълниците представят поддървета. Всеки връх има указател, сочещ към неговия родител. В дясната част е изобразено множеството след изпълнение на операцията Find-Set(a). В този случай всеки връх сочи директно към корена.

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

Оптимизация на Find:

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

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

Приложения редактиране

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

Свързани компоненти на неориентиран граф редактиране

Граф с четири свързани компонента : {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}

В реално изпълнение на алгоритъма за свързани компоненти, представителите на графа и структурата от данни за непресичащите се множества ще трябва да реферират помежду си. Това означава, че обект, представящ вектор, ще съдържа указател към кореспондиращия обект от несвързани множества, както и обратно. ^[1]

Алгоритъм на Крускал редактиране

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

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

^[1]

История редактиране

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

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

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

Източници редактиране

↑ ^а ^б Chapter 21: Data structures for Disjoint Sets // Introduction to Algorithms. Third. MIT Press, 2009. ISBN 978-0-262-53305-8. с. 561–585.

Тази страница частично или изцяло представлява превод на страницата Disjoint-set data structure в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[IntroductionToAlgorithms-1] а ^б Chapter 21: Data structures for Disjoint Sets // Introduction to Algorithms. Third. MIT Press, 2009. ISBN 978-0-262-53305-8. с. 561–585.

[1]