Union-Find (auch Disjoint-Set-Union oder DSU) ist eine Datenstruktur für disjunkte Mengen: Sie verwaltet Gruppen von Elementen, die sich nicht überlappen, und beantwortet zwei Fragen in praktisch konstanter Zeit:
- find(x) — zu welcher Gruppe gehört Element x? (Liefert den Repräsentanten der Gruppe.)
- union(x, y) — verschmilzt die Gruppen von x und y zu einer.
Die Idee: Bäume aus Mengen
Jede Gruppe wird als Baum gespeichert; die Wurzel des Baums ist der Repräsentant der Gruppe. Ein einfaches Array hält für jeden Knoten (hier: jedes Element) seinen Eltern-Knoten. find läuft von einem Element zur Wurzel, union hängt die eine Wurzel unter die andere.
Zwei Optimierungen machen Union-Find schnell
- Pfadkompression: Bei jedem find werden alle durchlaufenen Elemente direkt an die Wurzel gehängt — spätere finds sind damit kürzer.
- Union by Rank (oder Size): Die kleinere Gruppe wird immer an die größere gehängt, damit die Bäume flach bleiben.
Beide zusammen ergeben eine amortisierte Laufzeit von O(α(n)) pro Operation — α ist die inverse Ackermann-Funktion, die für alle praktischen Eingabegrößen kleiner als 5 ist. Die genaue Notation erklärt der Artikel Big-O-Notation.
Typische Anwendungen
- Kruskal-Algorithmus für den Minimalen Spannbaum: Kanten nach Gewicht sortieren und per union einfügen, wenn sie keinen Zyklus bilden.
- Zyklus-Erkennung in ungerichteten Graphen: Gehören zwei Endpunkte einer Kante bereits zur selben Gruppe, entsteht ein Zyklus.
- Verbundene Komponenten: Welche Knoten eines Netzes sind miteinander verbunden?
- Bildsegmentierung: benachbarte Pixel ähnlicher Farbe werden zu Regionen zusammengefasst.
Union-Find ist ein klassischer Baustein von Algorithmen; die Implementierung nutzt ein Array und oft Rekursion für find.
Verwandte Grundlagen: Minimaler Spannbaum, Graph-Datenstruktur, Knoten, Array, Algorithmus, Big-O-Notation.