Sistem de set dezarticulat

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 iunie 2017; verificările necesită 13 modificări .

Sistemul disjoint-set ( eng. disjoint -set , sau union-find data structure ) este o structură de date care vă permite să administrați un set de elemente, împărțit în subseturi disjunse. În acest caz, fiecărui subset i se atribuie reprezentantul său - un element al acestui subset. O structură abstractă de date este definită printr-un set de trei operații: . $\{\mathrm {Uniune} ,\mathrm {Găsiți} ,\mathrm {MakeSet} \)$

Este folosit pentru a stoca componentele conectate în grafice , în special, algoritmul lui Kruskal are nevoie de o structură de date similară pentru o implementare eficientă.

Definiție

Fie o mulțime finită împărțită în submulțimi care nu se intersectează ( clase ) : $S$ $X_{i}$

S=X_{0}\cup X_{1}\cup X_{2}\cup \ldots \cup X_{k}:X_{i}\cap X_{j}=\varnothing \quad \forall i ,j\in \lbrace 0,1,\ldots ,k\rbrace ,i\neq j

Fiecărui subset i se atribuie un reprezentant . Sistemul corespunzător de mulțimi disjunse suportă următoarele operații: $X_{i}$ $r_{i}\in X_{i}$

$\mathrm {MakeSet} (x)$ : creează un nou subset pentru element. Desemnează același element ca reprezentant al subsetului creat. $X$
$\mathrm {Uniune} (r,s)$ : combină ambele subseturi aparținând reprezentanților și , și desemnează reprezentantul noului subgrup. $r$ $s$ $r$
$\mathrm {Găsiți} (x)$ : Specifică pentru submulțimea căreia îi aparține elementul și returnează reprezentantul său. $x\în S$

Implementare algoritmică

O implementare trivială stochează proprietatea elementelor și reprezentanților într-o matrice de index . În practică, seturile de copaci sunt mai des folosite . Acest lucru poate reduce semnificativ timpul necesar operației de căutare . În acest caz, reprezentantul este scris la rădăcina arborelui, iar elementele rămase ale clasei sunt scrise în nodurile de sub acesta. $S$ $r_{i}$

$\mathrm {Uniune} (r,s)$ : atârnă rădăcina unui copac inferior sub rădăcina unui copac superior. Dacă acesta devine un copil al , ambele noduri sunt schimbate. $r$ $s$
$\mathrm {Găsiți} (x)$ : ia calea de la rădăcina arborelui și o întoarce (rădăcina în acest caz este o reprezentativă). $X$

Euristică

Euristice Union-By-Size , Union-By-Height , Random-Union și compresia căilor pot fi utilizate pentru a accelera operațiunile Union și Find .

În euristica Union-By-Size , în timpul operației, rădăcina copacului mai mic este atârnată sub rădăcina copacului mai mare. Această abordare păstrează echilibrul copacului. Adâncimea fiecărui subarbore nu poate depăși . Folosind această euristică, timpul de operare Find în cel mai rău caz crește de la la . Pentru o implementare eficientă, se propune stocarea numărului de noduri din arbore la rădăcină. $\mathrm {Uniune} (r,s)$ $T$ $\log \left|T\right|$ $O(\log n)$ $Pe)$

Euristica Union-By-Height este similară cu Union-By-Size , dar folosește înălțimea arborelui în loc de dimensiune.

Euristica Random-Union folosește faptul că este posibil să nu cheltuiți memorie suplimentară pentru a salva numărul de noduri din arbore: este suficient să alegeți rădăcina în mod aleatoriu - această soluție oferă o viteză la interogările aleatoare care este destul de comparabilă cu alte implementari. Cu toate acestea, dacă există multe interogări precum „unește un set mare cu unul mic”, această euristică îmbunătățește valoarea așteptată (adică timpul mediu de rulare) cu doar un factor de doi, așa că nu este recomandat să-l folosești fără euristica de compresie a căii. $Pe)$

Euristica de compresie a căii este utilizată pentru a accelera operația . Cu fiecare nouă căutare, toate elementele care se află pe calea de la rădăcină la elementul dorit sunt atârnate sub rădăcina arborelui. În acest caz, operația Find va funcționa în medie , unde este funcția inversă a funcției Ackerman . Acest lucru vă permite să accelerați semnificativ munca, deoarece pentru toate valorile utilizate în practică este nevoie de o valoare mai mică de 5. $\mathrm {Găsiți} (x)$ $\alpha (n)$ $\alfa$ $\alfa$

Exemplu de implementare

Implementare în C++:

const int MAXN = 1000 ; int p [ MAXN ], rang [ MAXN ]; void MakeSet ( int x ) { p [ x ] = x ; rang [ x ] = 0 ; } int Găsiți ( int x ) { return ( x == p [ x ] ? x : p [ x ] = Find ( p [ x ]) ); } void Uniune ( int x , int y ) { dacă ( ( x = Găsiți ( x )) == ( y = Găsiți ( y )) ) întoarcere ; dacă ( rang [ x ] < rang [ y ] ) p [ x ] = y ; else { p [ y ] = x ; dacă ( rang [ x ] == rang [ y ] ) ++ rang [ x ]; } }

Implementare în Free Pascal:

const MAX_N = 1000 ; var Parent , Rank : matrice [ 1 .. MAX_N ] din LongInt ; procedura de schimbare ( var x , y : LongInt ) ; var tmp : LongInt ; ÎNCEPE tmp := x ; x : = y y := tmp ; sfârşitul ; procedura MakeSet ( x : LongInt ) ; ÎNCEPE Părinte [ x ] := x ; Rang [ x ] := 0 ; sfârşitul ; function Find ( x : LongInt ) : LongInt ; ÎNCEPE dacă ( Părinte [ x ] <> x ) atunci Părinte [ x ] := Găsiți ( Părinte [ x ] ) ; Ieșire ( Părinte [ x ] ) ; sfârşitul ; procedura Union ( x , y : LongInt ) ; ÎNCEPE x := Găsiți ( x ) ; y := Găsiți ( y ) ; if ( x = y ) atunci exit () ; dacă ( Rang [ x ] < Rang [ y ] ) atunci schimbă ( x , y ) ; Parinte [ y ] := x ; dacă ( Rang [ x ] = Rang [ y ] ) atunci inc ( Rang [ x ] ) ; sfârşitul ;

Vezi și

Pădurea de mulțimi disjuncte

Literatură

Galler, Bernard A. și Michael J. Fisher. „Un algoritm de echivalență îmbunătățit”. // Communications of the ACM , 7.5 (1964): 301-303. (Engleză)
Tarjan, Robert E. și Jan Van Leeuwen. „Cel mai rău caz de analiză a algoritmilor de unire a seturilor”. // Jurnalul ACM 31.2 (1984): 245-281. (Engleză)
Thomas Kormen și colab.Algoritmi : Construcție și analiză = Introducere în algoritmi. - Ed. a II-a. - M .: „Williams” , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Link -uri

Union-Find / Kevin Wayne , Pearson-Addison Wesley
Capitolul 22: Structuri de date pentru seturi disjunctive / Introducere în algoritmi, Thomas H. Cormen, Charles E. Leiserson și Ronald L. Rivest
Vizualizator al lucrării unor structuri de date pentru mulțimi care nu se intersectează / ITMO
Implementarea seturilor disjunctive în C++ Boost Libraries Collection , 2006

Structuri de date
Liste	matrice listă legată individual listă dublu legată Lista de trecere
Copaci	B-arborele Arborele de căutare binar arborele AVL Copac roșu-negru morman
Contează	Graficul dirijat Graficul aciclic direcționat Diagrama de decizie binară Hipergraf
Alte	Tabel de hash Grămadă