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

edytuj

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

edytuj

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

edytuj

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  ). 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   (innymi słowy, sekwencja   operacji na tej strukturze dla   elementów działa łącznie w czasie  .

Ćwiczenia

edytuj

Podstawowe

edytuj

Zaawansowane

edytuj