Przejdź do zawartości

Struktury danych/Struktura Find-Union

Z Wikibooks, biblioteki wolnych podręczników.
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]