Union-Find-Datenstruktur

Die in diesem Blog verfassten Artikel wurden mit dem Ziel erstellt, zu unterrichten. Außerdem können die Informationen im Artikel falsch sein, also seien Sie bitte vorsichtig.

Union-Find ist eine Datenstruktur, die schnell prüft, ob mehrere Elemente zur gleichen Menge gehören, und zwei Mengen kombiniert. Disjunkte Mengenvereinigung, auch kurz DSU genannt.

Suchen Sie einen Vertreter als Eltern

class DisjointSet
{
public:
    explicit DisjointSet(int Count)
        : Parent(Count), Rank(Count, 0)
    {
        std::iota(Parent.begin(), Parent.end(), 0);
    }

    int Find(int Value)
    {
        if (Parent[Value] != Value)
        {
            Parent[Value] = Find(Parent[Value]);
        }

        return Parent[Value];
    }

    bool Unite(int A, int B)
    {
        A = Find(A);
        B = Find(B);

        if (A == B)
        {
            return false;
        }

        if (Rank[A] < Rank[B])
        {
            std::swap(A, B);
        }

        Parent[B] = A;

        if (Rank[A] == Rank[B])
        {
            ++Rank[A];
        }

        return true;
    }

private:
    std::vector<int> Parent;
    std::vector<int> Rank;
};

Die Pfadkomprimierung verbindet das übergeordnete Element während des Suchvorgangs direkt mit dem Vertreter. Union by Rank verhindert, dass die Tiefe zunimmt, indem ein niedrigerer Baum unter einem höheren Baum befestigt wird.

Wenn beide Optimierungen zusammen verwendet werden, verhält sich die Operation tatsächlich in nahezu konstanter Zeit.

Wo wird es verwendet?

• Überprüfen Sie, ob die beiden Regionen miteinander verbunden sind.
• Prüfen Sie, ob beim Hinzufügen einer Kante ein Zyklus auftritt.
• Erstellen Sie mit dem Kruskal-Algorithmus einen minimalen Spannbaum.
• Kombinieren Sie weiterhin Sets online.

Union-Find stellt den Pfad selbst nicht bereit. Es handelt sich um eine leistungsstarke Datenstruktur, wenn der Zweck in der Verbindung oder Zusammenführung von Sätzen besteht.