Veröffentlicht · wird verbessert
Algorithm
Union-Find (Disjoint-Set) verwaltet Elemente in disjunkten Gruppen und kann Gruppen vereinigen oder Zugehörigkeit nahezu in konstanter Zeit prüfen.
Union-Find, auch Disjoint-Set-Datenstruktur genannt, verwaltet eine Menge von Elementen, die in nicht überlappende Teilmengen zerlegt ist. Sie bietet nur zwei Operationen: find liefert den Repräsentanten der Menge, zu der ein Element gehört, und union vereinigt die Mengen zweier Elemente. Jede Menge wird als Baum aus Elternzeigern gespeichert; die Wurzel ist ihr Repräsentant.
Wenn Verbindungen nur hinzukommen und immer wieder gefragt wird, ob zwei Elemente verbunden sind, ist Union-Find deutlich schneller als jedes Mal den Graphen zu durchsuchen. Mit Pfadkompression und Vereinigung nach Rang oder Größe sinken die amortisierten Kosten pro Operation auf die inverse Ackermann-Funktion α(n), die für jede realistische Eingabe höchstens 4 beträgt. Die Struktur ist das Standardwerkzeug für Kruskals minimalen Spannbaum, Zykluserkennung, Zusammenhangskomponenten und Gruppierungsaufgaben wie das Zusammenführen von Konten und kommt häufig in Programmierinterviews vor.
Implementieren Sie zuerst find und union über ein einziges parent-Array und verfolgen Sie von Hand, wie ein Baum ohne Optimierungen zu einer Kette entartet. Fügen Sie dann Vereinigung nach Größe und Pfadkompression nacheinander hinzu und beobachten Sie, wie sich die Baumtiefe ändert. Lösen Sie anschließend Aufgaben zu Zusammenhangskomponenten, Zykluserkennung und Kruskal, um den Rückgabewert von union gezielt zu nutzen.
find folgt den Elternzeigern bis zur Wurzel, dem Repräsentanten, und union hängt eine Wurzel unter die andere, um zwei Mengen zu vereinigen.
find hängt besuchte Knoten direkt an die Wurzel und flacht den Baum ab, sodass spätere Aufrufe schneller werden.
Der kleinere Baum wird unter den größeren gehängt, wodurch die Höhe jedes Baums höchstens log n bleibt.
Mit beiden Optimierungen benötigen m Operationen O(m α(n)) Zeit; die inverse Ackermann-Funktion α(n) ist praktisch höchstens 4.
Die Klasse DSU speichert die Mengen in zwei Arrays, parent und size. find läuft die Elternzeiger hinauf und nutzt Pfadhalbierung, indem jeder Knoten an seinen Großelternknoten gehängt wird, damit die Bäume flach bleiben. union hängt die kleinere Menge unter die größere und gibt False zurück, wenn beide Elemente bereits in derselben Menge liegen. Das Beispiel fasst sechs Elemente zu drei Gruppen zusammen und gibt Zugehörigkeitsprüfungen sowie die Anzahl der Mengen aus.
union_find.py
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
dsu = DSU(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
dsu.union(a, b)
print(dsu.find(2) == dsu.find(0)) # True
print(dsu.find(4) == dsu.find(5)) # False
print(len({dsu.find(x) for x in range(6)})) # 3
python union_find.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Union-Find.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Union-Find aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.