Find and union

Ludzie od wieków grupują wszystko, co napotkają na swojej drodze. Każdy człowiek znajduje się w wielu grupach: paczce przyjaciół, rodzinie, klasie, szkole itd. W matematyce zamiast "grupy" będziemy mówić zbiory. Na dzisiejszej lekcji nauczymy się:

łączyć dwa zbiory
sprawdzać, czy dwa elementy są w tym samym zbiorze

Zbiory rozłączne

Każdemu zbiorowi przypiszemy dokładnie jednego reprezentanta. Mówiąc o reprezentancie elementu będę miał na myśli reprezentanta zbioru, do którego należy.

Reprezentant zbioru

Spostrzeżenie 1: Dwa elementy są w tym samym zbiorze wtedy, gdy mają takich samych reprezentantów.
Spostrzeżenie 2: Aby połączyć dwa zbiory wystarczy ustawić reprezentanta jednego z nich jako reprezentanta obu.

Łączenie zbiorów

Struktura zbiorów rozłącznych, inaczej Find & Union, umożliwia wykonywanie tych operacji. Zanim przejdziemy do jej omówienia, zdefiniujemy kilka pojęć:

rep[x] - jeśli $x$ jest swoim reprezentantem rep[x] = x; w przeciwnym wypadku rep[x] będzie "starać się" wskazywać na reprezentanta $x$
ile[x] - liczba elementów w zbiorze, którego reprezentantem jest $x$
Find(a) - funkcja, która zwraca reprezentanta elementu $a$
Union(a,b) - funkcja, która łączy zbiory, w których znajduje się $a$ i $b$

Żeby sprawdzić czy $a$ i $b$ są w tym samym zbiorze wystarczy sprawdzić, czy Find(a)=Find(b). Zauważmy, że mając funkcje Find(a) i Union(a,b), będziemy już umieli zrobić wszystko, czego chcieliśmy się dzisiaj nauczyć.

Na samym początku żadne dwa elementy nie są w tym samym zbiorze - każdy z nich tworzy jednoelementowy zbiór. Reprezentantem $x$ jest $x,$ rep[x]=x, a ile[x]=1

Stan początkowy

Łączenie zbiorów: Union

Załóżmy, że dla każdego $i$ rep[i] wskazuje na reprezentanta i. Union(2, 5)

Struktura po kilku wywołaniach union

void Union (int a,int b) {
    a = Find(a);
    b = Find(b);
    rep[a] = b;
    ile[b] += ile[a];
}

Niech $a$ i $b$ będą reprezentantami kolejno $A$ i $B.$ Żeby połączyć dwa zbiory ustawimy rep[a] na $b$ i zaktualizujemy wartość ile[b] dodając do niej ile[a].

Zbiór, zawierający element: Find

Zauważmy, że rep[a] "stara się" być reprezentantem $a$ - wskazuje albo na niego, albo na element, który kiedyś nim był. Co więcej rep[rep[a]], rep[rep[rep[a]]] itd. również się "starają", a każdemu z nich wychodzi to lepiej.

Szukanie reprezentanta zbioru

Jako, że łączymy w zbiory skończenie wiele elementów, istnieje takie rep[rep[rep[...rep[x]]]] będące reprezentantem $x.$ Wiemy również, że wskazuje on na samego siebie. Oznacza to, że możemy go znaleźć prostą rekurencją:

int Find (int a) {
    if (rep[a] == a)
        return a;
    return Find(a);
}

Wyżej opisane Find & Union działa poprawnie, ale istnieją przypadki, dla których będzie wolne. Zauważmy, że złożoność Union(a,b) jest taka sama, jak Find(a), która z kolei zależy tylko i wyłącznie od liczby wywołań rekurencyjnych. Chcielibyśmy aby była jak najmniejsza. Niestety przy obecnej implementacji może się zdarzyć, że będzie trwać nawet $O(n)$ . Dzieje się tak w przypadku, gdy wszystkie elementy są w jednym zbiorze i wartości rep[i] są parami różne. Wówczas Find(x) dla $x,$ który nie reprezentuje nikogo będzie kosztował nas $O(n)$ operacji.

Najbardizej niekorzystny find

Pomimo, że pojedyncze zapytanie o $x$ nie jest jeszcze aż tak czasochłonne, to jeśli spytamy się o niego wiele razy będziemy mieli duży problem.

Optymalizacja Union(A,B)

Jeżeli zawsze będziemy przypinać mniejszy zbiór do większego, to złożoność Find(x) dla dowolnego $x$ spadnie do $O(log \ n)$ .

Dowód: Zauważmy, że jeśli rep[x] != x, to wcześniej musieliśmy wywołać funkcję Union(x,rep[x]). \mbox{Oznacza to,} że liczba elementów w zbiorze rep[x] była nie mniejsza niż w zbiorze $x.$ ile[rep[x]] jest dwukrotnie większe od ile[x]. Wartości ile[i] nie mogą przekroczyć $n,$ więc kroków rekurencyjnych może być maksymalnie $O(log \ n)$ .

void Union (int a, int b) {
    if (ile[a] > ile[b])
        swap(a, b);
    rep[a] = b;
    ile[b] += ile[a];
}

Optymalizacja Find - skaracanie ścieżek

Kiedy raz znajdziemy reprezentanta a możemy od razu zaktualizować rep[a]. W ten sposób pominiemy konieczność wywoływania takich samych rekurencji wiele razy.

Kolejne operacje z aktualizowanie rep

Kolejne operacje z aktualizowanie rep - c.d.

int Find (int a) {
    if (rep[a] != a)
        rep[a] = Find(rep[a]);
    return rep[a];
}