DSU mit Pfadkompression

Disjoint Set Union (DSU), auch Union-Find genannt, ist eine Datenstruktur, die eine Sammlung disjunkter (nicht überlappender) Mengen verwaltet. Sie unterstützt zwei grundlegende Operationen: find (zu welcher Menge gehört Element x?) und union (die Mengen zusammenführen, die x und y enthalten). DSU eignet sich ideal für Probleme mit dynamischer Konnektivität, bei denen Gruppen im Laufe der Zeit zusammengeführt, aber nie aufgeteilt werden.

Jedes Element beginnt als eigene Menge. Während wir Kanten oder Beziehungen verarbeiten, führen wir Mengen zusammen. Die Herausforderung besteht darin, dies effizient zu tun — naive Implementierungen benötigen O(n) pro Operation, mit Optimierungen nähern wir uns amortisiert O(1).

In der naiven DSU läuft find(x) die Elternkette nach oben, bis sie einen Knoten erreicht, der auf sich selbst zeigt (die Wurzel). Ist der Baum balanciert, beträgt die Laufzeit O(log n). Wenn wir jedoch immer die zweite Wurzel unter die erste hängen, können wir eine Kette (degenerierten Baum) der Länge n erzeugen, wodurch jeder Aufruf von find O(n) benötigt.

Betrachten Sie die Vereinigungen 0→1→2→3→4 in dieser Reihenfolge. Der Aufruf von find für Knoten 0 muss die gesamte Kette durchlaufen. Mit Pfadkompression beseitigen wir dieses Problem, indem jeder besuchte Knoten während der find-Operation selbst direkt auf die Wurzel zeigt.

Pfadkompression verändert die find-Operation so, dass nach dem Finden der Wurzel jeder Knoten entlang des Pfads so aktualisiert wird, dass er direkt auf die Wurzel zeigt. Zukünftige find-Aufrufe für diese Knoten benötigen dann O(1). Die rekursive Variante erreicht dies elegant in einem einzigen Durchlauf.

Die entscheidende Erkenntnis: Nachdem der rekursive Aufruf die Wurzel zurückgegeben hat, setzen wir vor der Rückgabe self.parent[x] = root. Dadurch wird der Baum abgeflacht – alle Knoten auf dem Suchpfad zeigen nun direkt auf die Wurzel. Dies ändert nicht, zu welcher Menge ein Knoten gehört; es verkürzt lediglich zukünftige Suchpfade.

Die iterative Variante der Pfadkompression verwendet zwei Durchläufe: Im ersten Durchlauf wird die Kette nach oben durchlaufen, um die Wurzel zu finden; im zweiten Durchlauf wird jeder Knoten des Pfads erneut besucht und sein Elternknoten direkt auf die Wurzel gesetzt. Dadurch entfällt der Aufwand für den Rekursionsstack, und die Variante ist auch bei sehr tiefen Bäumen nahe am Rekursionslimit von Python sicher.

Bei beiden Ansätzen bleibt die Korrektheit unverändert – find gibt weiterhin dieselbe Wurzel zurück. Der einzige Unterschied besteht darin, dass die Elternzeiger als Nebeneffekt aktualisiert werden, wodurch alle zukünftigen find-Aufrufe für diese Knoten O(1) benötigen.

Allein die Pfadkompression erreicht über eine Folge von m Operationen eine amortisierte Laufzeit von O(log n) pro Operation. Eine find-Operation kann beim ersten Durchlaufen einer Kette teuer sein, flacht diese Kette jedoch ab, sodass jeder spätere find-Aufruf für diese Knoten O(1) benötigt. Die Gesamtkosten verteilen sich auf viele Operationen.

Die formale Analyse verwendet die Potenzialmethode: Das Potenzial der DSU sinkt jedes Mal, wenn sich der Elternpfad eines Knotens verkürzt, und diese Verringerung bezahlt die Kosten des Durchlaufens. Ohne Union by Rank liefert die Pfadkompression allein eine amortisierte Laufzeit von O(log n) – bereits eine enorme Verbesserung gegenüber dem naiven O(n).

Eine häufige Anwendung der DSU ist das Zählen zusammenhängender Komponenten in einem Graphen. Wir initialisieren einen Zähler components mit n (einen Zähler pro Knoten). Jede erfolgreiche Union-Operation (das Zusammenführen zweier verschiedener Mengen) verringert den Zähler um 1. Am Ende enthält der Zähler die Anzahl der verschiedenen Komponenten.

Das ist effizienter, als für Zusammenhangsabfragen BFS oder DFS auszuführen, insbesondere wenn Kanten schrittweise (online) eintreffen. Die DSU verarbeitet jede Kante unabhängig vom Zeitpunkt ihres Eintreffens in nahezu O(1) amortisierter Zeit.

Das Problem Number of Provinces gibt eine n×n-Adjazenzmatrix vor und fragt, wie viele Gruppen direkt oder indirekt verbundener Städte existieren. Das ist genau ein Problem zur Bestimmung zusammenhängender Komponenten, das sich mit DSU elegant lösen lässt. Wir durchlaufen alle Paare (i, j), für die isConnected[i][j] == 1 gilt, und rufen union(i, j) auf.

Nach der Verarbeitung aller Verbindungen ist dsu.components die gesuchte Antwort. Das ist einfacher und schneller, als von jedem noch nicht besuchten Knoten aus eine BFS zu starten, und verarbeitet die Matrixdarstellung direkt, ohne zuvor eine Adjazenzliste erstellen zu müssen.

Neben der Kompression in zwei Durchläufen gibt es eine einfachere Variante in einem Durchlauf, die Pfadhalbierung genannt wird: Während wir die Kette nach oben durchlaufen, lassen wir jeden Knoten auf seinen Großelternknoten statt auf seinen Elternknoten zeigen. Dadurch wird die Pfadlänge bei jedem Durchlauf halbiert, ohne dass ein zweiter Durchlauf erforderlich ist. In Kombination mit Union by Rank wird dieselbe amortisierte Komplexität von O(alpha(n)) erreicht.

Pfadhalbierung wird beim Competitive Programming häufig bevorzugt, weil sie aus einer einzigen übersichtlichen Schleife besteht und weder Rekursion noch einen zweiten Durchlauf benötigt. Jeder Schritt führt self.parent[x] = self.parent[self.parent[x]]; x = self.parent[x] aus.

Um zu prüfen, ob zwei Knoten zusammenhängend sind (also zur selben Komponente gehören), rufen Sie find(x) == find(y) auf. Wenn beide Aufrufe dieselbe Wurzel zurückgeben, gehören die Knoten zur selben Komponente. Diese Zusammenhangsabfrage benötigt mit Pfadkompression amortisiert nahezu O(1) Zeit.

In Interviewaufgaben treten Zusammenhangsabfragen häufig zwischen Union-Operationen auf. DSU verarbeitet beides online – Sie können Union-Operationen und Abfragen in beliebiger Reihenfolge abwechseln. Das unterscheidet DSU von Algorithmen für statische Graphen wie BFS/DFS, die nach jeder strukturellen Änderung erneut ausgeführt werden müssen.

Ein häufiger Fehler besteht darin, find aufzurufen und anschließend parent falsch zu verändern. Rufen Sie immer find für beide Elemente auf, bevor Sie sie auf Gleichheit prüfen – andernfalls vergleichen Sie möglicherweise einen Knoten fälschlicherweise mit seiner eigenen Wurzel. Ein weiterer Fehler besteht darin zu vergessen, dass union keine Wirkung haben sollte, wenn beide Elemente bereits dieselbe Wurzel besitzen.

In Python kann das Rekursionstiefenlimit (standardmäßig 1000) bei großen Ketten mit rekursivem find einen RecursionError verursachen. Verwenden Sie entweder die iterative Variante mit zwei Durchläufen, erhöhen Sie das Limit mit sys.setrecursionlimit oder verwenden Sie die iterative Pfadhalbierung, um tiefe Rekursion vollständig zu vermeiden.

Bei manchen Problemen benötigen Sie die Größe jeder Komponente und nicht nur ihre Wurzel. Fügen Sie ein size-Array hinzu, das mit lauter 1en initialisiert wird. Beim Zusammenführen zweier Komponenten addieren Sie die Größe der kleineren Wurzel zur größeren Wurzel. Dadurch sind Abfragen der Komponentengröße nach jeder Union-Operation in O(1) möglich.

Die Größenverwaltung bildet auch die Grundlage für Union by Size (eine Alternative zu Union by Rank): Hängen Sie den kleineren Baum immer unter die Wurzel des größeren Baums. Dadurch bleibt die Baumhöhe garantiert bei O(log n), was dieselbe asymptotische Garantie wie Union by Rank liefert.

Testen Sie Ihr Verständnis der Konzepte von Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.

In dieser Lektion haben Sie gelernt: DSU verwaltet disjunkte Mengen mit den Operationen find und union, Pfadkompression flacht den Baum ab, indem sie alle durchlaufenen Knoten direkt auf die Wurzel zeigen lässt, und dadurch wird für find eine amortisierte Laufzeit von nahezu O(1) erreicht. Als Nächstes betrachten wir Union by Rank, das Bäume von oben nach unten flach hält, um die Schranke der inversen Ackermann-Funktion zu erreichen.