Hallo,
kann jemand ein Beispiel geben, wo ich diese Datenstruktur in der Praxis brauche ?
Es geht ja darum Mengen zu verwalten. Zwei Mengen können verschmolzen werden oder eine Menge wird zurückgegeben, wenn ich ein bestimmtes Element suche.
Grüße,
Tris
Hi Tris,
also wenn du zum Beispiel möchtest du wissen ob Knoten miteinander verbunden sind, dann kann man dies mit der Union Find Struktur gut parallelisieren. Man geht von jedem Knoten zu einem möglichen nächsten Knoten und macht dann ein Union über die Knotenpaare.
Von diesen Knotenpaaren ausgehend kann man dann weiter verknüpfen. Zum Schluss weiss man über die Mengen, welche Knoten miteinander verbunden sind.
Gruss Peter
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
allgemein ist dient diese Datenstruktur zur Repräsentierung von Äquivalenzklassen / Partitionierungen. Q-Bert hat ja schon ein gutes Bsp. genannt. Üblich ist häufig bei der Suche nicht die Menge zurückzuliefern, die das gesuchte Element enthält sondern einen fixen Repräsentanten davon (die Vereinigung liefert dann entsprechend einen neuen Repräsentanten für die zusammengeführten Partition/Äquivalenzklassen).
Gruss
Enno
Hallo,
ich habe gelesen, dass die Mengen intern als Bäume dargestellt werden mit dem Repräsentanten als Wurzel, wobei alle Knoten einen Zeiger auf den Elter haben. Wenn ich über die FindSet(x)-Operation den Repräsentanten von x haben will, dann gehe ich über die Zeiger bis zur Wurzel hin. Die Frage ist nun, wie ich überhaupt an das x komme ? Ich meine das x muss ich ja erstmal finden bevor ich den Pfad bis zur Wurzel verfolgen kann.
Grüße,
Tris
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Hallo,
man kann die Mengen als Bäume darstellen. Die Annahme dabei ist üblicherweise, das x neben seinem Wert auch einen Verweis auf seinen Vaterknoten hat, d.h. man rechnet mit Knoten des Baums und nicht mit dem puren x. Math. ausgedrückt - x ist sich seiner Äquivalenzklasse / Partition „bewußt“. Am Bsp. der Erreichbarkeit - hier würden anfangs alle Knoten des Graphens als einelementige Partitionen / Bäume aufgefaßt, die schrittweise vereinigt werden. Man rechnet also von Anfang an mit Partitionen und nicht mit den Elementen an sich.
Gruss
Enno