Tekst źródłowy strony Struktury danych/Struktura Find-Union

{{Struktury danych/SpisTreści}}
==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 <code>Find</code>, <code>Union</code> oraz<code> MakeSet</code>:

{{Struktury danych:ADT|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ć:
*[[w:Algorytm_Kruskala |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 <math>O(n)</math>). 
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 <math>O(\log n)</math> (innymi słowy, sekwencja <math>m</math> operacji na tej strukturze dla <math>n</math> elementów działa łącznie w czasie <math>O(m + n \log n)</math>.
===Ćwiczenia===
{{TODO|Ćwiczenia}}
====Podstawowe====
====Zaawansowane====
{{Nawigacja|Struktury danych|[[Struktury danych/Kopce|Kopce]]|[[Struktury danych/Tablice z haszowaniem|Tablice z haszowaniem]]}}