Struktury danych/Struktura Find-Union

Spis treści
Wstęp	Wstęp - Konwencje
Struktury danych	Podstawy - Tablice - Listy - Stosy - Kolejki - Drzewa - Zbiory - Kopce - Find-Union - Tablice z haszowaniem - Grafy
Dodatki	Złożoność obliczeniowa - Implementacje w C++ - Implementacje w Pascalu - Bibliografia - Dla twórców podręcznika

Find-Union

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 trzy operacje Find, Union oraz MakeSet:

Find-Union

• 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.
• MakeSet: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).

Zastosowania

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.

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(\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)$.