Zbieranie zbiorów w bliskiej stałości czasu

Dwa operacje, jedna las

Struktura zbiorów rozłącznych (union-find) utrzymuje zbiór elementów podzielony na nieprzecinające się grupy i szybko odpowiada na dwie pytania: find(x) - w której grupie jest x? - oraz union(x, y) - łączy grupę x z grupą y. Internale każda grupa to drzewo, a każdy element przechowuje tylko wskaźnik do swojego rodzica. Węzeł drzewa jest kanonicznym reprezentantem grupy: dwa elementy są w tej samej grupie dokładnie kiedy ich korzenie pasują.

Algorytm Kruskala dla minimalnego drzewa rozpinającego to klasyczny przypadek użycia: sortuje krawędzie pod względem wag, a następnie przechodzi po nich w rosnącej kolejności i dodaje krawędź do drzewa, chyba że jej dwie końce są już połączone - pytanie, na które union-find odpowiada w czasie potrzebnym do przejścia dwóch krótkich łańcuchów do ich korzeni. Taka sama struktura śledzi komponenty spójne podczas przybywania krawędzi po jednej, wykrywa cykle w grafie i łączy regiony w segmentacji obrazu.

Proste rozwiązanie i dlaczego się zdegeneruje

Pierwsza próba polegała na tym, że find przeszuka węzły rodzicielskie do korzenia, a union łączył jeden korzeń pod drugim losowo. To działa, ale nic nie zapobiega temu, aby drzewo stało się długą listą - union elementy w zwiększonym porządku, zawsze łącząc nowy korzeń pod poprzednim, i otrzymujesz proste liniowe n węzłów. Find kosztuje wtedy O(n) zamiast O(log n) lub lepszego czasu, który na самом fakcie chcesz uzyskać.

function find(x) {
  while (parent[x] !== x) x = parent[x];
  return x;
}
function union(x, y) {
  const rx = find(x), ry = find(y);
  if (rx !== ry) parent[rx] = ry;   // arbitrary attachment - can chain badly
}

Unia według rangi

Rozwiązanie polega na zawsze przypinaniu drzewa o mniejszej głębokości pod drzewo o większej głębokości. Podczas śledzenia śledź albo dokładną wielkość, albo górne ograniczenie rangi (w przybliżeniu, wysokości drzewa) dla każdego korzenia; podczas łączenia, korzeń o mniejszej rangi staje się dzieckiem korzenia o większej rangi, a remisy zwiększają rangę zwycięzcy o jeden. To same ogranicza wysokość każdego drzewa do O(log n), ponieważ drzewo o rangi r może być utworzone tylko przez łączenie dwóch drzew o rangi r-1, więc potrzebne jest co najmniej 2 do potęgi r elementów, aby osiągnąć rangę r.

Kompresja ścieżki: przysiłanie podczas przebiegu

Unia według rang ogranicza wysokość, ale można zrobić znacznie lepsze przez ponowne zapisywanie historii przy każdym przejściu do korzenia. Kompresja ścieżki sprawia, że każdy węzeł odwiedzony podczas operacji find() wskazuje bezpośrednio na korzeń po znalezieniu tego korzenia, co oznacza, że kolejne operacje find() z tych węzłów są O(1).

```function find(x) { if (parent[x] !== x) parent[x] = find(parent[x]); // przysiłanie bezpośrednio do korzenia return parent[x]; }``` Tarjan i van Leeuwen udowodnili, że kombinacja unii według rang z kompresją ścieżki prowadzi do kosztu amortyzowanego dowolnej sekwencji m operacji na n elementach dążącego do O(m · α(n)), gdzie α jest odwrotnością szybko rosnącej funkcji Ackermann. Dla każdego praktycznego n, α(n) wynosi co najwyżej 4 lub 5, co oznacza, że struktura zachowuje się tak, jakby każda operacja była O(1) - rzadki przypadek, w którym prawdziwa granica niekonstancja jest nierozróżnialna od czasu stałego na danych rzeczywistych.

function find(x) {
  if (parent[x] !== x) parent[x] = find(parent[x]);   // point straight at the root
  return parent[x];
}

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Union-Find — Disjoint Sets & Path Compression i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.