Struktura zbiorów rozłącznych

Z Wikipedii

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).

Spis treści 1 Implementacja listowa 2 Implementacja przez las zbiorów rozłącznych 3 Historia 4 Linki zewnętrzne

[edytuj] Implementacja listowa

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 jest oczywista, 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(logn) (innymi słowy, sekwencja m operacji na tej strukturze dla n elementów działa łącznie w czasie O(m + nlogn).

[edytuj] Implementacja przez las zbiorów rozłącznych

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)
     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(logn). 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α(m,n)), gdzie n jest liczbą elementów uniwersum, zaś α bardzo wolno rosnącą odwrotnością funkcji Ackermanna (we wszystkich praktycznych sytuacjach α(m,n) < 6).

[edytuj] Historia

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ę α, wcześniej najlepsze było ograniczenie podane przez Johna Hopcrofta i Jeffrey'a Ullmana, wynoszące O(log^* n) (logarytm iterowany, log^* n, to inna funkcja wolno rosnąca, choć nie tak wolno jak funkcja α). Tarjan i van Leeuwen opracowali także jednoprzejściowy algorytm Find, który w praktyce jest bardziej efektywny.

[edytuj] Linki zewnętrzne

• Compaq Research: Zeus: Animation of Union-Find Algorithms
• Java applet: A Graphical Union-Find Implementation, Rory L. P. McGuire
• The abstract data type Union-Find, prosta implementacja w C, Vašek Chvátal
• Union-Find - notatki i implementacja, Rafał Nowak

• 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