Union-Find (Disjoint Set Union)

MAKE-SET legt eine einzelnelementige Menge an, FIND(x) liefert den internen Repräsentanten der Menge von x, und UNION(x,y) verschmilzt zwei Mengen, sofern sie verschieden sind. Zusammen halten diese Operationen eine Partition in disjunkte Komponenten aktuell. Der Repräsentant ist nur eine technische Kennung; er muss weder kleinstes Element noch dauerhaft stabil sein. Union–Find gibt außerdem keine Wegroute und keine sortierte Elementliste zurück. Wer eine stabile fachliche Bezeichnung der Komponente braucht, kann sie separat speichern und nach einer Vereinigung aktualisieren. Die Bedeutung der Kennung kann sich ändern, wenn später weitere Vereinigungen erfolgen.

Union nach Rang oder Größe hängt den flacheren Baum unter den tieferen; dadurch wächst die Höhe kontrolliert. Pfadkompression verkürzt anschließend die Elternketten der bei FIND besuchten Knoten. Zusammen ergeben die Verfahren für m Operationen auf n Elementen amortisiert O(m α(n)) Zeit. Die inverse Ackermannfunktion wächst extrem langsam, ist aber formal nicht konstant. Die Schranke setzt beide Optimierungen und die üblichen Union–Find-Operationen voraus. Die Rangheuristik darf nach Pfadkompression eine obere Schranke bleiben; die exakte aktuelle Höhe muss sie nicht abbilden. Die Schranke wird häufig als nahezu konstante amortisierte Zeit je Operation zusammengefasst.

FIND ist nicht bei jedem einzelnen Aufruf garantiert exakt O(1). Vor der Kompression kann eine Suche mehrere Elternzeiger durchlaufen. Die bekannte nahezu konstante Laufzeit ist eine amortisierte Aussage über eine Operationsfolge: Frühe längere Wege werden durch Pfadkompression für spätere Suchen verkürzt. Für eine saubere Analyse sollte man daher O(α(n)) amortisiert pro Operation angeben, statt die praktische Kurzform „konstant“ als strikte Worst-Case-Garantie zu lesen. Die formale Schranke bezieht sich auf die Operationsfolge und schließt nicht aus, dass einzelne FIND-Aufrufe länger dauern.

Die gewöhnliche Struktur kann Mengen zusammenführen, aber keine beliebigen Löschungen oder Aufteilungen rückgängig machen. Nach einer Vereinigung enthält der Elternwald nicht genug Information, um jede frühere Trennung effizient zu rekonstruieren. Benötigt eine dynamische Konnektivitätsaufgabe auch Kantenlöschungen, braucht sie ein spezialisiertes Offline- oder voll dynamisches Verfahren. Union–Find bleibt passend, wenn sich Komponenten ausschließlich vereinigen und die Abfragen nach Repräsentanten erfolgen. Für Rücksetzen innerhalb von Suchbäumen wird häufig ein Änderungsprotokoll verwendet; beliebige Splits sind damit nicht automatisch unterstützt. Die Einschränkung betrifft die Operationsmenge und nicht bloß die Implementierungsdetails.

Kruskal sortiert die Kanten nach Gewicht und prüft vor jeder Aufnahme, ob die Endpunkte bereits verbunden sind. Sind FIND(u) und FIND(v) verschieden, verbindet die Kante zwei Komponenten ohne Zyklus; danach vereinigt UNION(u,v) sie. Union–Find liefert genau diesen Konnektivitätstest effizient. Die Datenstruktur wählt jedoch weder die Kantengewichte aus noch beweist sie allein, dass die Greedy-Auswahl einen minimalen Spannbaum ergibt; dafür braucht man zusätzlich Kruskals Austauschargument. Der Korrektheitsbeweis für den minimalen Spannbaum ist von der Laufzeit der Komponentenanfrage logisch getrennt. Damit beantwortet die Struktur eine notwendige Teilfrage von Kruskal, nicht dessen gesamten Beweis.