data-structures
Union-Find-Datenstruktur

Einführung

Theorie

Union-Datenstrukturen bieten folgende Vorgänge:

• make_sets(n) initialisiert eine Union-Find-Datenstruktur mit n Singletons
• find(i) gibt einen Vertreter für die Menge von Element i
• union(i,j) die Sets zusammen, die i und j

Wir repräsentieren unsere Partition der Elemente 0 bis n - 1 indem wir für jedes Element i ein übergeordnetes Element parent[i] speichern, das schließlich zu einem Vertreter der Menge führt, die i .
Wenn ein Element selbst ein Vertreter ist, ist es sein eigenes Elternteil, dh parent[i] == i .

Wenn wir also mit Singleton-Sets beginnen, ist jedes Element ein eigener Vertreter:

Wir können den Vertreter für eine gegebene Menge finden, indem Sie einfach diesen übergeordneten Zeigern folgen.

Lassen Sie uns nun sehen, wie wir Sets zusammenführen können:
Wenn Sie die Elemente 0 und 1 und die Elemente 2 und 3 zusammenführen möchten, können Sie dies tun, indem Sie den übergeordneten Wert von 0 auf 1 und den übergeordneten Wert von 2 auf 3 setzen:

In diesem einfachen Fall müssen nur die übergeordneten Elemente des Elements selbst geändert werden.
Wenn Sie jedoch größere Mengen zusammenführen möchten, müssen Sie immer den übergeordneten Zeiger des Repräsentanten der Menge ändern, der in eine andere Menge zusammengeführt werden soll: Nach dem Zusammenführen (0,3) haben wir den übergeordneten Vertreter des Satzes festgelegt dem Vertreter der Gruppe, die 3 enthält, 0 enthält

Um das Beispiel etwas interessanter zu machen, lassen Sie uns jetzt auch (4,5), (5,6) und (3,4) zusammenführen :

Der letzte Begriff, den ich einführen möchte, ist die Pfadkomprimierung :
Wenn wir den Vertreter eines Satzes finden möchten, müssen wir möglicherweise mehrere übergeordnete Zeiger verfolgen, bevor Sie den Vertreter erreichen. Wir können dies erleichtern, indem Sie den Vertreter für jedes Set direkt in seinem übergeordneten Knoten speichern. Wir verlieren die Reihenfolge, in der wir die Elemente zusammengeführt haben, können jedoch möglicherweise einen großen Laufzeitgewinn erzielen. In unserem Fall sind die einzigen Pfade, die nicht komprimiert sind, die Pfade von 0, 4 und 5 bis 3:

Grundlegende Implementierung

Die grundlegendste Implementierung einer Union-Find-Datenstruktur besteht aus einem parent Array, das ein übergeordnetes Element für jedes Element der Struktur speichert. Nach diesen übergeordneten "Zeigern" für ein Element führt i zu dem Vertreter j = find(i) der Menge, die i , wobei parent[j] = j gilt.

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
        }
    }
};

Verbesserungen: Pfadkomprimierung

Wenn wir viele merge für eine Datenstruktur mit Union-Find durchführen, sind die von den parent Zeigern dargestellten Pfade möglicherweise recht lang. Die Pfadkompression ist , wie bereits im Theorieteil beschrieben, eine einfache Möglichkeit, dieses Problem zu mildern.

Wir könnten versuchen, nach jeder k- ten Merge-Operation oder etwas Ähnlichem eine Pfadkomprimierung für die gesamte Datenstruktur durchzuführen, aber eine solche Operation kann eine recht lange Laufzeit haben.

Daher wird die Pfadkomprimierung meist nur für einen kleinen Teil der Struktur verwendet, insbesondere für den Pfad, den wir entlanggehen, um den Repräsentanten eines Satzes zu finden. Dies kann durch Speichern des Ergebnisses des erfolgen find Betrieb nach jedem rekursiven subcall:

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
}

Verbesserungen: Union nach Größe

In unserer aktuellen Implementierung von merge wählen wir immer die linke Menge als Kind der rechten Menge, ohne die Größe der Mengen zu berücksichtigen. Ohne diese Einschränkung, die Pfade (Pfad ohne Kompression) von einem Element zu sein Vertreter könnte ziemlich lang sein, was zu einer großen Laufzeiten auf den führenden find Anrufe.

Eine weitere häufige Verbesserung ist daher die Vereinigung nach Größenheuristik, die genau das tut, was sie sagt: Wenn zwei Sätze zusammengefügt werden, wird immer der größere Satz als übergeordneter Satz des kleineren Satzes festgelegt, was eine Pfadlänge von höchstens ergibt Schritte:

Wir speichern ein zusätzliches Element std::vector<size_t> size in unserer Klasse, das für jedes Element auf 1 initialisiert wird. Beim Zusammenfügen von zwei Sätzen wird der größere Satz zum übergeordneten Element des kleineren Satzes, und wir summieren die beiden Größen:

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
    }

Verbesserungen: Union nach Rang

Eine andere Heuristik, die üblicherweise anstelle der Vereinigung nach Größe verwendet wird, ist die Vereinigung nach Rangheuristik

Die Grundidee ist, dass wir nicht wirklich die exakte Größe der Mengen speichern müssen. Eine Annäherung an die Größe (in diesem Fall: ungefähr der Logarithmus der Größe der Menge) reicht aus, um dieselbe Geschwindigkeit zu erreichen wie die Vereinigung nach Größe.

Dazu führen wir den Begriff des Rangs einer Menge ein, der wie folgt gegeben ist:

• Singletons haben den Rang 0
• Wenn zwei Sätze mit ungleichem Rang zusammengeführt werden, wird der Satz mit dem höheren Rang zum übergeordneten Element, während der Rang unverändert bleibt.
• Wenn zwei Sätze gleichen Ranges zusammengefügt werden, wird einer von ihnen zum Elternteil des anderen (die Wahl kann beliebig sein), und der Rang wird erhöht.

Ein Vorteil von Union nach Rang ist die Speicherplatznutzung: Da der maximale Rang in etwa steigt Bei allen realistischen Eingabegrößen kann der Rang in einem einzigen Byte gespeichert werden (da n < 2^255 ).

Eine einfache Implementierung von Union nach Rang könnte folgendermaßen aussehen:

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];
        }
    }

Endgültige Verbesserung: Union nach Rang mit Out-of-Bounds-Speicher

Während in Kombination mit Pfad Kompression, Vereinigung von Rang nahezu konstante Zeit Operationen an erreicht Datenstrukturen gewerkschafts findet, gibt es einen letzten Trick, uns loszuwerden, die erhalten kann rank durch Speicher den Ranges in Out-of-bounds Einträgen von insgesamt Speichern das parent Array. Es basiert auf den folgenden Beobachtungen:

• Wir müssen den Rang eigentlich nur für Vertreter speichern, nicht für andere Elemente. Für diese Vertreter brauchen wir kein parent .
• Bisher hat parent[i] höchstens die size - 1 , dh größere Werte werden nicht verwendet.
• Alle Ränge sind höchstens .

Dies bringt uns zu folgendem Ansatz:

• Anstelle der Bedingung parent[i] == i identifizieren wir jetzt Repräsentanten mit
  parent[i] >= size
• Wir verwenden diese Out-of-Bound-Werte, um die Rangstufen der Menge zu speichern, dh die Menge mit dem Repräsentanten i hat die Ranggröße parent[i] - size
• Daher initialisieren wir das übergeordnete Array mit parent[i] = size anstelle von parent[i] = i , dh jeder Satz ist sein eigener Repräsentant mit Rang 0.

Da wir nur die Rangwerte von Offset - size , können wir einfach den ersetzen rank Vektor durch die parent bei der Umsetzung von Vektor merge und müssen nur die Bedingung zu identifizieren Vertreter auszutauschen find :

Abgeschlossene Implementierung mit Union nach Rang und Pfad-Komprimierung:

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];
        }
    }
};