data-structures
Struktura danych znajdź związek

Wprowadzenie

Teoria

Unijne struktury danych zapewniają następujące operacje:

• make_sets(n) inicjuje strukturę danych znajdowania związku z n singletonami
• find(i) zwraca reprezentanta dla zestawu elementu i
• union(i,j) scala zbiory zawierające i i j

Reprezentujemy naszą partycję elementów od 0 do n - 1 , przechowując element nadrzędny element parent[i] dla każdego elementu i co ostatecznie prowadzi do reprezentanta zbioru zawierającego i .
Jeśli sam element jest reprezentatywny, jest on własnym rodzicem, tzn. parent[i] == i .

Zatem jeśli zaczniemy od zestawów singletonów, każdy element jest własnym reprezentantem:

Możemy znaleźć przedstawiciela dla danego zestawu, po prostu przestrzegając tych wskaźników nadrzędnych.

Zobaczmy teraz, jak możemy łączyć zestawy:
Jeśli chcemy scalić elementy 0 i 1 oraz elementy 2 i 3, możemy to zrobić, ustawiając element nadrzędny od 0 do 1 i ustawiając element nadrzędny od 2 do 3:

W tym prostym przypadku należy zmienić tylko sam wskaźnik nadrzędny elementu.
Jeśli jednak chcemy scalić większe zestawy, musimy zawsze zmienić wskaźnik nadrzędny przedstawiciela zestawu, który ma zostać scalony w inny zestaw: Po scaleniu (0,3) ustawiliśmy element nadrzędny przedstawiciela zestawu zawierający 0 do przedstawiciela zestawu zawierającego 3

Aby uczynić przykład nieco bardziej interesującym, połączmy teraz (4,5), (5,6) i (3,4) :

Ostatnim pojęciem, które chcę wprowadzić, jest kompresja ścieżki :
Jeśli chcemy znaleźć przedstawiciela zestawu, być może będziemy musieli zastosować kilka wskaźników nadrzędnych przed dotarciem do przedstawiciela. Możemy to ułatwić, przechowując reprezentanta dla każdego zestawu bezpośrednio w ich węźle nadrzędnym. Tracimy kolejność, w której scaliliśmy elementy, ale potencjalnie możemy uzyskać duży wzrost czasu działania. W naszym przypadku jedynymi ścieżkami, które nie są skompresowane, są ścieżki od 0, 4 i 5 do 3:

Podstawowa implementacja

Najbardziej podstawowa implementacja struktury danych znajdowania związku składa się z elementu parent tablicy przechowującego element nadrzędny dla każdego elementu struktury. Podążanie za tymi nadrzędnymi „wskaźnikami” dla elementu i prowadzi nas do reprezentatywnego j = find(i) zbioru zawierającego i , gdzie parent[j] = j .

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;  // Parent for every node

public:
    union_find(size_t n) : parent(n) {
        for (size_t i = 0; i < n; ++i)
            parent[i] = i;      // Every element is its own representative
    }

    size_t find(size_t i) const {
        if (parent[i] == i)     // If we already have a representative
            return i;           // return it
        return find(parent[i]); // otherwise return the parent's representative
    }

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi != pj) {        // If the elements are not in the same set: 
            parent[pi] = pj;   // Join the sets by marking pj as pi's parent
        }
    }
};

Ulepszenia: Kompresja ścieżki

Jeśli wykonamy wiele operacji merge w strukturze danych znajdowania związku, ścieżki reprezentowane przez wskaźniki parent mogą być dość długie. Kompresja ścieżki , jak już opisano w części teoretycznej, jest prostym sposobem na złagodzenie tego problemu.

Możemy spróbować wykonać kompresję ścieżki dla całej struktury danych po każdej k- tej operacji scalania lub czegoś podobnego, ale taka operacja może mieć dość długi czas działania.

Tak więc kompresja ścieżki jest najczęściej stosowana tylko na niewielkiej części konstrukcji, szczególnie na ścieżce, którą idziemy, aby znaleźć reprezentanta zbioru. Można to zrobić, przechowując wynik operacji find po każdym rekurencyjnym wywołaniu:

size_t find(size_t i) const {
    if (parent[i] == i)          // If we already have a representative
        return i;                // return it
    parent[i] = find(parent[i]); // path-compress on the way to the representative
    return parent[i];            // and return it
}

Ulepszenia: Unia według wielkości

W naszej bieżącej implementacji merge zawsze wybieramy lewy zestaw, aby był dzieckiem zestawu prawidłowego, bez uwzględnienia jego rozmiaru. Bez tego ograniczenia ścieżki (bez kompresji ścieżki ) od elementu do jego przedstawiciela mogą być dość długie, co prowadzi do dużych czasów wykonywania przy wywołaniach find .

Innym powszechnym ulepszeniem jest zatem heurystyka sumowania według wielkości , która robi dokładnie to, co mówi: Łącząc dwa zestawy, zawsze ustawiamy większy zestaw jako element nadrzędny mniejszego zestawu, co prowadzi do co najwyżej długości ścieżki kroki:

W naszej klasie przechowujemy dodatkowy element członkowski std::vector<size_t> size który jest inicjowany na 1 dla każdego elementu. Po scaleniu dwóch zestawów większy zestaw staje się rodzicem mniejszego zestawu i sumujemy dwa rozmiary:

private:
    ...
    std::vector<size_t> size;

public:
    union_find(size_t n) : parent(n), size(n, 1) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {            // If the elements are in the same set: 
            return;                // do nothing
        }
        if (size[pi] > size[pj]) { // Swap representatives such that pj
            std::swap(pi, pj);     // represents the larger set
        }
        parent[pi] = pj;           // attach the smaller set to the larger one
        size[pj] += size[pi];      // update the size of the larger set
    }

Ulepszenia: Unia według rangi

Inną heurystyką powszechnie stosowaną zamiast zjednoczenia według wielkości jest zjednoczenie według heurystyki według rang

Jego podstawową ideą jest to, że tak naprawdę nie musimy przechowywać dokładnego rozmiaru zestawów, przybliżenie rozmiaru (w tym przypadku: z grubsza logarytm rozmiaru zestawu) wystarcza, aby osiągnąć taką samą prędkość jak połączenie według rozmiaru.

W tym celu wprowadzamy pojęcie rangi zbioru, które jest podane następująco:

• Singletony mają rangę 0
• Jeśli dwa zestawy o nierównej randze zostaną połączone, zestaw o większej randze staje się rodzicem, a pozycja pozostaje niezmieniona.
• Jeśli dwa zestawy o równej randze zostaną połączone, jeden z nich stanie się rodzicem drugiego (wybór może być dowolny), jego pozycja zostanie zwiększona.

Jedną zaletą łączenia według rangi jest wykorzystanie przestrzeni: gdy maksymalna ranga rośnie mniej więcej tak , dla wszystkich realistycznych rozmiarów wejściowych, pozycja może być zapisana w jednym bajcie (od n < 2^255 ).

Prosta implementacja unii według rang może wyglądać następująco:

private:
    ...
    std::vector<unsigned char> rank;

public:
    union_find(size_t n) : parent(n), rank(n, 0) { ... }

    ...

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (rank[pi] < rank[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (rank[pi] > rank[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++rank[pi];
        }
    }

Ostateczne ulepszenie: Łączenie według rangi z przechowywaniem poza granicami

Podczas gdy w połączeniu z kompresją ścieżki, łączenie według rang prawie osiąga stałe operacje czasowe na strukturach danych znajdowania związku, istnieje ostatnia sztuczka, która pozwala nam całkowicie pozbyć się pamięci rank poprzez przechowywanie rangi we wpisach poza zakresem tablica parent . Opiera się na następujących spostrzeżeniach:

• W rzeczywistości musimy przechowywać ranking tylko dla przedstawicieli , a nie dla innych elementów. W przypadku tych przedstawicieli nie musimy przechowywać parent .
• Jak dotąd parent[i] ma co najwyżej size - 1 , tzn. Większe wartości nie są używane.
• Wszystkie stopnie są co najwyżej .

To prowadzi nas do następującego podejścia:

• Zamiast warunku parent[i] == i , teraz identyfikujemy przedstawicieli według
  parent[i] >= size
• Używamy tych wartości poza zakresem do przechowywania rang zbioru, tj. Zestaw z reprezentatywnym i ma pozycję parent[i] - size
• W ten sposób inicjujemy macierz parent[i] = size zamiast parent[i] = i , tzn. Każdy zestaw jest własnym reprezentantem o randze 0.

Ponieważ kompensujemy tylko wartości rangi o size , możemy po prostu zastąpić wektor rank wektorem parent w implementacji merge i wystarczy jedynie wymienić warunek identyfikujący przedstawicieli w find :

Zakończono implementację z użyciem unii według kompresji rang i ścieżek:

using std::size_t;

class union_find {
private:
    std::vector<size_t> parent;

public:
    union_find(size_t n) : parent(n, n) {} // initialize with parent[i] = n

    size_t find(size_t i) const {
        if (parent[i] >= parent.size()) // If we already have a representative
            return i;                   // return it
        return find(parent[i]);         // otherwise return the parent's repr.
    }

    void merge(size_t i, size_t j) {
        size_t pi = find(i);
        size_t pj = find(j);
        if (pi == pj) {
            return;
        }
        if (parent[pi] < parent[pj]) {
            // link the smaller group to the larger one
            parent[pi] = pj;
        } else if (parent[pi] > parent[pj]) {
            // link the smaller group to the larger one
            parent[pj] = pi;
        } else {
            // equal rank: link arbitrarily and increase rank
            parent[pj] = pi;
            ++parent[pi];
        }
    }
};