Struktury danych/Struktura Find-Union

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:

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