Struktura zbiorów rozłącznych

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 | edytuj kod]

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(\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 | edytuj kod]

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 | edytuj kod]

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 | edytuj kod]

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

Linki zewnętrzne[edytuj | edytuj kod]