Struktura zbiorów rozłącznych

Struktura zbiorów rozłącznych to struktura danych, która przechowuje dla ustalonego zbioru (uniwersum) jego podział na mniejsze, rozłączne zbiory. Struktura taka umożliwia dwie operacje:

Find: Wyznacza, w którym zbiorze jest dany element, pozwalając na sprawdzenie, czy dwa elementy są w tym samym zbiorze.
Union: Łączy dwa zbiory w jeden.

Czasem podaje się jeszcze trzecią operację, MakeSet, która dołącza do uniwersum nowy element jako jednoelementowy zbiór.

Operacje te potrzebują jakiejś metody identyfikacji i odróżniania od siebie zbiorów. Najczęściej używa się w tym celu jednego, wyróżnionego elementu zbioru (zwanego reprezentantem).

Implementacja listowa edytuj

Prostym sposobem implementacji zbiorów rozłącznych jest zapamiętanie każdego zbioru jako listy. Reprezentantem zbioru jest pierwszy element na liście. Operacja MakeSet polega na utworzeniu listy jednoelementowej, Union polega na połączeniu list (tym samym działając w czasie stałym), niestety, Find wymaga w pesymistycznym przypadku przeszukania wszystkich list (czas $O(n)$ ).

Możliwą modyfikacją tej metody jest trzymanie w każdym węźle listy wskaźnika do jej początku – wtedy Find działa w czasie stałym, zaś Union wymaga poprawienia takich wskaźników na jednej z łączonych list. Jeśli dołącza się zawsze mniejszą listę do większej, operacja Union działa w zamortyzowanym czasie $O(\log n)$ (innymi słowy, sekwencja $m$ operacji na tej strukturze dla $n$ elementów działa łącznie w czasie $O(m+n\log n)$ ).

Implementacja przez las zbiorów rozłącznych edytuj

Inną techniką implementacji jest użycie tzw. lasów zbiorów rozłącznych. Każdy zbiór jest reprezentowany jako drzewo skierowane, którego korzeń jest reprezentantem. W najprostszej wersji operacje wyglądają następująco:

 function MakeSet(x)
     x.parent := null
 
 function Find(x)
     if x.parent == null
        return x
        
     return Find(x.parent)
 
 function Union(x, y)
     xRoot = Find(x)
     yRoot = Find(y)
     if xRoot != yRoot
         xRoot.parent := yRoot

Tworzone w ten sposób drzewa mogą być bardzo niezrównoważone, operacja Find nie musi zatem działać w tej implementacji lepiej niż w listowej (czyli $O(n),$ gdzie $n$ jest liczbą elementów; Union działa w tej implementacji tak samo szybko). Są jednak dwie techniki znacznie poprawiające złożoność:

Pierwsza, zwana łączeniem według rangi, polega na dołączaniu mniejszego drzewa do korzenia większego drzewa. Dla oceny, które drzewo jest większe, używamy heurystycznego sposobu zwanego rangą: pojedynczy element drzewa ma rangę zero, a kiedykolwiek łączymy dwa drzewa o równej randze $r,$ rangę powstałego drzewa ustalamy na $r+1.$

Z tą poprawką złożoność obu operacji wynosi $O(\log n).$ Odpowiedni pseudokod wygląda tak:

 function MakeSet(x)
     x.parent := null
     x.rank   := 0
 
 function Union(x, y)
     xRoot = Find(x)
     yRoot = Find(y)
     if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot != yRoot
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1

Drugie udoskonalenie, zwane kompresją ścieżki, polega na spłaszczaniu struktur drzewa zawsze, kiedy używamy Find. Każdy węzeł, który napotykamy na naszej drodze podczas szukania korzenia jest natychmiast przepinany tak, aby korzeń był jego ojcem. Tym samym każde następne szukanie reprezentanta będzie znacznie szybsze. Oto poprawiony kod Find:

 function Find(x)
     if x.parent == null
        return x
  
     x.parent = Find(x.parent)
     return x.parent

Obie techniki stosowane łącznie powodują, że łączny czas $m$ operacji Find i Union jest $O(m\alpha (m,n)),$ gdzie $n$ jest liczbą elementów uniwersum, zaś $\alpha$ bardzo wolno rosnącą odwrotnością funkcji Ackermanna (we wszystkich praktycznych sytuacjach $\alpha (m,n)<6$ ).

Historia edytuj

Algorytm ten pierwszy raz opisali Galler i Fisher w 1964, jednak długo nie były znane ograniczenia na jego czas działania. Robert Tarjan był pierwszym, który znalazł oszacowanie przez funkcję $\alpha$ (odwrotność funkcji Ackermanna), wcześniej najlepsze było ograniczenie podane przez Johna Hopcrofta i Jeffreya Ullmana, wynoszące O(log^* n) (logarytm iterowany, log^* n, to inna funkcja wolno rosnąca, choć nie tak wolno jak funkcja $\alpha$ ). Tarjan i van Leeuwen opracowali także jednoprzejściowy algorytm Find, który w praktyce jest bardziej efektywny.

Zastosowania edytuj

Wiele algorytmów grafowych powszechnie używa tej struktury, m.in.

Algorytm Kruskala, Algorytm Borůvki – wyznaczanie minimalnego drzewa rozpinającego graf spójny nieskierowany
Algorytm znajdywania składowych spójnych grafu nieskierowanego

Linki zewnętrzne edytuj

Compaq Research: Zeus: Animation of Union-Find Algorithms. research.compaq.com. [zarchiwizowane z tego adresu (2005-02-05)].
Rory L. P. McGuire, Java applet: A Graphical Union-Find Implementation
Vašek Chvátal, The abstract data type Union-Find, prosta implementacja w C
Rafał Nowak, Union-Find – notatki i implementacja
Sprawdź własną implementację na SPOJ-u.
Bernard A. Galler and Michael J. Fisher. An improved equivalence algorithm. Communications of the ACM, Volume 7, Issue 5 (May 1964), 301-303. Pierwsza praca o implementacji przez las zbiorów rozłącznych. ACM Digital Library
Zvi Galil and Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems, ACM Computing Surveys, Volume 23, Issue 3 (September 1991), 319-344. ACM Digital Library