Sumowanie zbiorów rozłącznych

Niekiedy przydatne okazuje się grupowanie elementów w rozłączne zbiory. Struktura danych dla zbiorów rozłącznych pozwala zarządzać taką rodziną dynamicznych (tzn. zmieniających się w czasie) zbiorów rozłącznych. Do każdego zbioru odwołujemy się przez jego reprezentanta (zazwyczaj jest to jakiś element tego zbioru), przy czym wymagamy, żeby dwa zapytania o reprezentanta danego zbioru dawały taki sam wynik, jeśli w międzyczasie sam zbiór się nie zmieniał. Do dyspozycji mamy trzy operacje:

• MakeSet(x): tworzy nowy jednoelementowy zbiór { x }, którego reprezentantem jest oczywiście x (zakładamy, że x nie należy do żadnego innego zbioru w rodzinie);
• Find(x): zwraca reprezentanta zbioru, do którego należy x;
• Union(x,y): łączy dwa zbiory, których reprezentantami są x i y, w nowy zbiór będący ich teoriomnogościową sumą; dwa pierwotne zbiory (zakładamy, że były różne) są przy tym niszczone.

W naszych rozważaniach dotyczących kosztów powyższych operacji w różnych implementacjach struktury danych dla zbiorów rozłącznych będziemy brali pod uwagę dwa parametry: n, czyli łączną liczbę operacji MakeSet (bez straty ogólności można założyć, że wszystkie te operacje są wykonywane na początku), oraz m, czyli łączną liczbę wszystkich operacji MakeSet, Find i Union (w szczególności mamy \( n\le m \)). Nietrudno zauważyć, że liczba operacji Union nie jest większa niż n-1 (bo każda z nich zmniejsza liczbę zbiorów w rodzinie o jeden).

Większość zastosowań struktur danych dla zbiorów rozłącznych sprowadza się do zarządzania pewną dynamicznie rozrastającą się relacją równoważności (jej klasy abstrakcji to nasze zbiory rozłączne). Jako przykłady można wymienić:

• algorytm Kruskala znajdowania minimalnego drzewa rozpinającego;
• rozpoznawanie spójnych składowych w dynamicznie rozrastającym się grafie nieskierowanym;
• generowanie labiryntów;
• rozpoznawanie obszarów na obrazach w postaci cyfrowej.