Union-Find Quick Union

Für eine Datenmenge unterstützt die Union-Find-Datenstruktur hauptsächlich zwei Operationen:

  • union(p,q) - Verbindet die beiden Elemente p und q miteinander.

  • find(p)- Fragt ab, zu welcher Menge das Element p gehört.

  • isConnected(p,q)- Prüft, ob die beiden Elemente p und q verbunden sind.

Im vorherigen Unterabschnitt verwendeten wiridzur Darstellung der Union-Find-Menge in Array-Form; die Zeitkomplexität der find-Operation beträgt in der tatsächlichen NutzungO(1), aber die Verbindungseffizienz war nicht hoch.

In diesem Unterabschnitt implementieren wir die Union-Find-Menge auf eine andere Weise. Betrachten Sie jedes Element als einen Knoten, der auf seinen Elternknoten zeigt, und der Wurzelknoten zeigt auf sich selbst. Wie in der folgenden Abbildung dargestellt, zeigt Knoten 3 auf Knoten 2, was bedeutet, dass 3 und 2 verbunden sind; Knoten 2 selbst ist der Wurzelknoten, also zeigt er auf sich selbst.

Wir verwenden ebenfalls ein Array, um die Union-Find-Menge darzustellen, aber die folgende Gruppe von Elementen verwendetparent, um den Elternknoten darzustellen, auf den das aktuelle Element zeigt. Jedes Element zeigt auf sich selbst, und alle sind unabhängig.

Wenn man zu diesem Zeitpunktunion(4,3)ausführt, lassen Sie Element 4 auf Element 3 zeigen:

Das Array ändert sich entsprechend:

Um festzustellen, ob zwei Elemente verbunden sind, müssen Sie nur prüfen, ob ihre Wurzelknoten gleich sind.

Wie in der folgenden Abbildung dargestellt, sind die Wurzelknoten von Knoten 4 und Knoten 9 beide 8, also sind sie verbunden.

Um zwei Elemente zu verbinden, müssen Sie nur ihre entsprechenden Wurzelknoten finden und die Wurzelknoten verbinden; dann werden sie zu verbundenen Knoten.

Angenommen, wir möchten 6 und 4 in der obigen Abbildung verbinden; wir müssen nur den Wurzelknoten 5 von 6 auf den Wurzelknoten 8 von 4 zeigen lassen.

Um eine solche Baumstruktur aufzubauen, die auf Elternknoten zeigt, verwenden Sie ein Array, um einen Baum aufzubauen, der auf Elternknoten zeigt; parent[i] repräsentiert den Elternknoten, auf den Element i zeigt.

...
private int[] parent;
private int count;  // Anzahl der Datenelemente
...

Suchvorgang: Um die Mengennummer zu finden, die Element p entspricht, fragt man fortlaufend seinen Elternknoten ab, bis man den Wurzelknoten erreicht. Der Wurzelknoten ist durch parent[p] == p gekennzeichnet, mit O(h)-Komplexität, wobei h die Höhe des Baums ist.

...
private int find(int p){
    assert( p >= 0 && p < count );
    while( p != parent[p] )
        p = parent[p];
    return p;
}
...

Um die Mengen zu vereinigen, zu denen Element p und Element q gehören, findet man jeweils die Wurzelknoten der beiden Elemente und lässt einen Wurzelknoten auf den anderen Wurzelknoten zeigen; dann sind die beiden Mengen vereinigt. Diese Operation hat eine Zeitkomplexität von O(h), wobei h die Höhe des Baums ist.

public void unionElements(int p, int q){
    int pRoot = find(p);
    int qRoot = find(q);
    if( pRoot == qRoot )
        return;
    parent[pRoot] = qRoot;
}

Java-Beispielcode

Quellcode-Paket-Download:Herunterladen

Code der Datei UnionFind2.java:

package example.union;
/**
* Zweite Version von UnionFind
 */
public class UnionFind2 {
    // Unsere zweite Version von Union-Find verwendet ein Array, um einen Baum aufzubauen, der auf Elternknoten zeigt
    // parent[i] repräsentiert den Elternknoten des i-ten Elements
    private int[] parent;
    private int count;  // Anzahl der Datenelemente
    // Konstruktor
    public UnionFind2(int count){
        parent = new int[count];
        this.count = count;
        // Initialisierung: Jedes parent[i] zeigt auf sich selbst, was bedeutet, dass jedes Element eine eigene Menge bildet
        for( int i = 0 ; i < count ; i ++ )
            parent[i] = i;
    }
    // find-Prozess, finde die Mengennummer, die dem Element p entspricht
    // O(h)-Komplexität, h ist die Höhe des Baums
    private int find(int p){
        assert( p >= 0 && p < count );
        // den Elternknoten weiter abfragen, bis der Wurzelknoten erreicht ist
        // Eigenschaft des Wurzelknotens: parent[p] == p
        while( p != parent[p] )
            p = parent[p];
        return p;
    }
    // prüfen, ob Element p und Element q zu derselben Menge gehören
    // O(h)-Komplexität, h ist die Höhe des Baums
    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }
    // die Mengen, die Element p und Element q enthalten, zusammenführen
    // O(h)-Komplexität, h ist die Höhe des Baums
    public void unionElements(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if( pRoot == qRoot )
            return;
        parent[pRoot] = qRoot;
    }
}
Weitere Erweiterungen