Union-Find Quick Find

Dieser Abschnitt führt die grundlegenden Operationen basierend auf der Disjoint-Set-Union-Struktur aus dem vorherigen Abschnitt ein: Abfrage, Vereinigung und Bestimmung, ob Elemente verbunden sind.

Abfrage der Mengen-ID eines Elements und direkte Rückgabe.idArray-Wert,O(1)Zeitkomplexität.

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

Die Menge zusammenführen, zu der Elementpund Elementqgehören. Der Vereinigungsvorgang erfordert das Durchlaufen aller Elemente und dann das Zusammenführen der Mengen-IDs der beiden Elemente. Dieser Vorgang hat ...O(n)Komplexität.

...
public void unionElements(int p, int q) {
    int pID = find(p);
    int qID = find(q);
    if (pID == qID)
        return;
    for (int i = 0; i < count; i++)
        if (id[i] == pID)
            id[i] = qID;
}
...

Java-Beispielcode

Quellpaket herunterladen:Herunterladen

UnionFind1.java Datei-Code:

package example.union;

/**
* Erste Version von Union-Find
 */
public class UnionFind1 {
    // Unsere erste Version von Union-Find ist im Wesentlichen ein Array
    private int[] id;
    // Anzahl der Datenelemente
    private int count;

    public UnionFind1(int n) {
        count = n;
        id = new int[n];
        // Initialisierung: Jedes id[i] zeigt auf sich selbst, keine zusammengeführten Elemente
        for (int i = 0; i < n; i++)
            id[i] = i;
    }

    // find-Prozess, finde die Mengennummer, die dem Element p entspricht
    private int find(int p) {
        assert p >= 0 && p < count;
        return id[p];
    }

    // prüfen, ob Element p und Element q zu derselben Menge gehören
    // O(1)-Komplexität
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    // die Mengen, die Element p und Element q enthalten, zusammenführen
    // O(n)-Komplexität
    public void unionElements(int p, int q) {

        int pID = find(p);
        int qID = find(q);

        if (pID == qID)
            return;

        // Der Merge-Prozess muss alle Elemente einmal durchlaufen und die Mengen-IDs der beiden Elemente zusammenführen
        for (int i = 0; i < count; i++)
            if (id[i] == pID)
                id[i] = qID;
    }
}
Weitere Erweiterungen