Union-Find (Disjunkte Menge) erklärt, mit Code

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

Was ist Union-Find?

Union-Find, auch Disjoint Set Union (DSU) genannt, ist eine Datenstruktur, die eine Menge von Elementen verwaltet, die in nicht überlappende Gruppen aufgeteilt sind. Jedes Element gehört zu genau einer Gruppe, und jede Gruppe wird durch einen einzigen Repräsentanten identifiziert, ihre Wurzel.

Der Trick liegt darin, wie die Gruppen gespeichert werden: als Wald von Bäumen. Jedes Element hält einen Elternzeiger, und dem Elternteil nach oben zu folgen, führt stets zur Wurzel der Gruppe. Zwei Elemente sind genau dann in derselben Gruppe, wenn sie dieselbe Wurzel teilen. Das ist die ganze Idee, und alles andere dreht sich darum, sie schnell zu machen.

Die zwei Operationen

Union-Find unterstützt genau zwei Operationen, und sein ganzer Ruf beruht darauf, beide fast augenblicklich auszuführen.

• find(x) gibt die Wurzel der Gruppe zurück, die x enthält, indem es den Elternzeigern nach oben folgt. Zwei Elemente sind verbunden, wenn find(a) == find(b).
• union(a, b) vereinigt die beiden Gruppen, indem eine Wurzel zum Elternteil der anderen gemacht wird.

Da Gruppen sich nur vereinigen und nie teilen, ist Union-Find perfekt für Probleme, bei denen Verbindungen mit der Zeit hinzukommen, aber nie entfernt werden.

Die naive Variante und ihr Problem

Ein erster Versuch speichert nur Elternzeiger und vereinigt, indem eine Wurzel auf die andere zeigt. Es funktioniert, hat aber einen üblen Schwachpunkt: nichts hindert die Bäume daran, zu langen Ketten zu wachsen. Stapelt jede Vereinigung einen Knoten auf den letzten, muss find eine Kette der Länge n ablaufen, und jede Operation verschlechtert sich auf O(n).

Das ist nicht besser als eine einfache Liste. Die Lösung sind zwei kleine Änderungen, die zusammen zu den gefeiertsten Ergebnissen der Datenstrukturen zählen.

Zwei Optimierungen, die alles ändern

Union by Rank hält Bäume flach. Beim Vereinigen zweier Gruppen wird stets der kürzere Baum unter die Wurzel des höheren gehängt. Ein kurzer Baum, der an einem hohen hängt, erhöht die Höhe nicht, sodass die Bäume flach bleiben.

Pfadkompression flacht unterwegs ab. Jedes Mal, wenn find zu einer Wurzel hinaufläuft, richtet es jeden passierten Knoten direkt auf diese Wurzel. Das nächste find auf einem von ihnen ist dann ein einziger Sprung. Die Abbildung unten zeigt, wie ein find eine Kette kollabieren lässt.

Zusammen verwendet halten Union by Rank und Pfadkompression jeden Baum fast völlig flach, sodass beide Operationen in nahezu konstanter Zeit laufen. Jede allein hilft; beide zusammen machen Union-Find berühmt.

Implementierung in Python

Die gesamte Struktur passt in eine kleine Klasse. Zwei Arrays erledigen die ganze Arbeit: parent und rank.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # jedes Element beginnt als eigene Wurzel
        self.rank = [0] * n            # eine obere Schranke für die Höhe jedes Baums

    def find(self, x):
        # Pfadkompression: x direkt auf die Wurzel richten.
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # bereits in derselben Gruppe

        # Union by Rank: den kürzeren Baum unter den höheren hängen.
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

Beachten Sie, dass union False zurückgibt, wenn die beiden Elemente bereits verbunden waren. Dieser eine Boolean macht Zyklenerkennung und Kruskals Algorithmus so sauber: schlägt eine Vereinigung fehl, hätte die Kante, die Sie hinzufügen wollten, einen Zyklus geschlossen.

Komplexität: fast konstant

Mit beiden Optimierungen läuft eine Folge von m Operationen auf n Elementen insgesamt in O(m · α(n)), wobei α die inverse Ackermann-Funktion ist.

Die inverse Ackermann-Funktion wächst so langsam, dass α(n) für jedes n, das ins beobachtbare Universum passt, höchstens 4 ist. In der Praxis behandeln Sie jede Operation als konstante Zeit. Wie sich das unter alle Graphenalgorithmen einordnet, sehen Sie im Komplexitätsleitfaden und im Spickzettel.

Wo es verwendet wird

Union-Find taucht überall dort auf, wo Sie den Zusammenhang verfolgen müssen, während er wächst.

• Kruskals minimaler Spannbaum: sortiere die Kanten und füge jede nur hinzu, wenn ihre Endpunkte in verschiedenen Gruppen liegen. Union-Find ist die Zyklusprüfung. Siehe minimale Spannbäume.
• Zyklenerkennung in einem ungerichteten Graphen: teilen bei einer Kante beide Endpunkte bereits eine Wurzel, schließt die Kante einen Zyklus.
• Zusammenhangskomponenten: vereinige jede Kante und zähle dann die verschiedenen Wurzeln.
• Dynamischer Zusammenhang und Interviews: Aufgaben wie Number of Provinces, Redundant Connection und Accounts Merge sind allesamt verkapptes Union-Find. Siehe Graphenalgorithmen für Programmierinterviews.

Es liegt außerdem in Etappe 3 des Graphentheorie-Lernpfads, genau dort, wo Sie Spannbäume lernen.