imported>Hpod: log -> log_2

2024-08-29T09:53:59Z

log -> log_2

Neue Seite

Eine '''Union-Find-Datenstruktur''' verwaltet die [[Partition (Mengenlehre)|Partition]] einer [[Menge (Mathematik)|Menge]]. Der [[Abstrakter Datentyp|abstrakte Datentyp]] wird durch die Menge der drei Operationen ''{Union, Find, Make-Set}'' gebildet. Union-Find-Strukturen dienen zur Verwaltung von Zerlegungen in disjunkte Mengen. Dabei bekommt jede Menge der Zerlegung ein kanonisches Element zugeordnet, welches als Name der Menge dient. ''Union'' vereinigt zwei solche Mengen, ''Find(x)'' bestimmt das kanonische Element derjenigen Menge, die ''x'' enthält, und ''Make-Set'' erzeugt eine Elementarmenge ''{x}'' mit dem kanonischen Element ''x''.

== Definition ==
Eine endliche Menge <math>S</math> sei in die [[disjunkt]]en [[Klasse (Mengenlehre)|Klassen]] <math>X_i</math> partitioniert:

:<math>S = X_0 \uplus X_1 \uplus X_2 \uplus \ldots \uplus X_k</math> mit <math>X_i \cap X_j = \varnothing \quad\forall i, j \in \lbrace 0, 1, \ldots, k \rbrace, i \neq j</math>.

Zu jeder Klasse <math>X_i</math> wird ein Repräsentant <math>r_i \in X_i</math> ausgewählt.
Die zugehörige Union-Find-Struktur unterstützt die folgenden Operationen effizient:
* Init(<math>S</math>): Initialisiert die Struktur und bildet für jedes <math>x \in S</math> eine eigene Klasse mit <math>x</math> als Repräsentant.
* Union(<math>r</math>, <math>s</math>): Vereinigt die beiden Klassen, die zu den beiden Repräsentanten <math>r</math> und <math>s</math> gehören, und bestimmt <math>r</math> zum neuen Repräsentanten der neuen Klasse.
* Find(<math>x</math>): Bestimmt zu <math>x \in S</math> den eindeutigen Repräsentanten, zu dessen Klasse <math>x</math> gehört.

== Implementierung ==
Eine triviale Implementierung speichert die Zugehörigkeiten zwischen den Elementen aus <math>S</math> und den Repräsentanten <math>r_i</math> in einem [[Feld (Datentyp)|Array]]. Für kürzere Laufzeiten werden jedoch in der Praxis Mengen von [[Baum (Graphentheorie)|Bäumen]] verwendet. Dabei werden die Repräsentanten in den [[Wurzel (Graphentheorie)|Wurzeln]] der Bäume gespeichert, die anderen Elemente der jeweiligen Klasse in den [[Knoten (Graphentheorie)|Knoten]] darunter.

* Union(<math>x</math>, <math>y</math>): Hängt die Wurzel des niedrigeren Baumes als neues Kind unter die Wurzel des höheren Baumes (gewichtete Vereinigung). Falls nun <math>x</math> Kind von <math>y</math> ist, werden <math>x</math> und <math>y</math> vertauscht.
* Find(<math>x</math>): Wandert vom Knoten <math>x</math> aus den Pfad innerhalb des Baumes nach oben bis zur Wurzel und gibt diese als Ergebnis zurück.

== Heuristiken ==
Um die Operationen ''Find'' und ''Union'' zu beschleunigen, gibt es die [[Heuristik]]en ''union by size, union by rank'' (Rang- und Größenheuristik) und ''Pfadkompression'', wobei sich ''union by size'' und ''union by rank'' gegenseitig ausschließen und ''union by rank'' oft in Kombination mit ''Pfadkompression'' verwendet wird.

=== {{Anker|size}} Union by size ===
Bei der [[Operation (Informatik)|Operation]] ''Union(r,s)'' wird der [[Baum (Graphentheorie)|Baum]], der in Summe weniger Knoten hat, sprich kleiner ist, unter den größeren Baum gehängt. Damit verhindert man, dass einzelne Teilbäume zu Listen entarten können wie bei der naiven Implementation (r wird in jedem Fall Wurzel des neuen Teilbaums). Die Tiefe eines Teilbaums T kann damit nicht größer als <math>\log_2 \left|T\right|</math> werden. Mit dieser Heuristik verringert sich die Worst-Case-Laufzeit von ''Find'' von <math>O(n)</math> auf <math>O(\log n)</math>. Für eine effiziente Implementation führt man bei jeder Wurzel die Anzahl der Elemente im Teilbaum mit.

=== {{Anker|rank}} Union by rank ===
Wird ausschließlich die Heuristik ''union by rank'' verwendet, entspricht der Rang (''rank'') einer Wurzel der Höhe ihres Unter[[Baum (Graphentheorie)|baumes]].
Es wird stets der Baum mit dem niedrigeren Rang dem mit dem höheren angehängt. Bei gleichem Rang kann die Verkettung der Bäume beliebig gewählt werden. Somit kann der Rang eines Knoten nur wachsen, wenn zwei Bäume des gleichen Rangs aneinander gehängt werden.

Daraus folgt insbesondere:
* Knoten ohne Kinder haben den Rang 0
* Wenn die zu kombinierenden [[Baum (Graphentheorie)|Bäume]] den gleichen Rang haben, ist der Rang der resultierenden Baumes um 1 größer

Man kann zur weiteren Effizienzsteigerung ''union by rank'' in Kombination mit ''Pfadkompression'' verwenden. In diesem Fall wird deutlich, weshalb die Bezeichnung des Rangs anstelle der der Tiefe verwendet wird: Die ''Pfadkompression'' verringert die Höhe von Bäumen, während ihr Rang bestehen bleibt. Siehe auch ''Pfadkompression''.<ref>[https://algorithms.tutorialhorizon.com/disjoint-set-union-find-algorithm-union-by-rank-and-path-compression/ Disjoint Set | Union-Find Algorithm – Union by rank and path compression]. In: algorithms.tutorialhorizon.com (englisch)</ref><ref>{{Webarchiv|url=http://www.mathblog.dk/disjoint-set-data-structure/ |wayback=20161202120715 |text=Disjoint-set data structure |archiv-bot=2023-02-02 09:07:22 InternetArchiveBot }}. In: mathblog.dk</ref>

==== Pseudocode ====
'''function''' ''Union''(''x'', ''y'')
{
''// Knoten durch die Wurzeln des Baums ersetzen''
''x'' = ''Find''(''x'');
''y'' = ''Find''(''y'');
'''if''' (''x'' = ''y'') ''// Wenn x und y schon zur selben Menge gehören, wird die Funktion verlassen''
{
'''return;'''
}
'''if''' (''x''.rank < ''y''.rank) ''// Wenn der Rang von x kleiner als der Rang von y ist, wird y zur neuen Wurzel''
{
''x''.parent = ''y'';
}
'''else if''' (''x''.rank > ''y''.rank) ''// Wenn der Rang von x größer als der Rang von y ist, wird x zur neuen Wurzel''
{
''y''.parent = ''x'';
}
'''else''' ''// Wenn die Ränge gleich sind, wird y zur neuen Wurzel und der Rang von y inkrementiert''
{
''x''.parent = ''y'';
''y''.rank = ''y''.rank + 1;
}
}

=== Pfadkompression ===
Um spätere ''Find(x)''-Suchvorgänge zu beschleunigen, versucht man die Wege vom besuchten Knoten zur zugehörigen Wurzel zu verkürzen.

==== Maximale Verkürzung (Wegkompression) ====
Nach dem Ausführen von ''Find(x)'' werden alle Knoten auf dem Pfad von ''x'' zur Wurzel direkt unter die Wurzel gesetzt. Man beachte hierbei, dass die Operation ''Union(x,y)'' die Operation ''Find(x)'' verwendet. Dieses Verfahren bringt im Vergleich zu den beiden folgenden den größten Kostenvorteil für nachfolgende Aufrufe von Find für einen Knoten im gleichen Teilbaum. Zwar muss dabei jeder Knoten auf dem Pfad zwischen Wurzel und ''x'' zweimal betrachtet werden, für die [[Zeitkomplexität|asymptotische Laufzeit]] ist das jedoch egal.

==== Pseudocode ====
'''function''' ''Find''(''x'')
{
'''if''' (''x''.parent ≠ ''x'')
{
''x''.parent = ''Find''(''x''.parent);
'''return''' ''x''.parent;
}
'''else'''
{
'''return''' ''x'';
}
}

== Aufteilungsmethode (splitting) ==
Während des Durchlaufes lässt man jeden Knoten auf seinen bisherigen Großvater zeigen, falls vorhanden. Damit wird ein durchlaufender Pfad in zwei der halben Länge zerlegt.

=== Halbierungsmethode (halving) ===
Während des Durchlaufes lässt man jeden zweiten Knoten auf seinen bisherigen Großvater zeigen.

Diese Methoden haben beide dieselben amortisierten Kosten wie die oberste Kompressionsmethode (Knoten unter die Wurzel schreiben). Alle Kompressionsmethoden beschleunigen zukünftige ''Find(x)''-Operationen.

== Laufzeiten ==
Union-Find-Datenstrukturen ermöglichen die Ausführung der obigen Operationen mit den folgenden [[Laufzeit (Informatik)|Laufzeiten]] (<math>n=\left| S \right|</math>):

Triviale Implementierung mit einem Array A (A[i] = x: Knoten i liegt in der Menge x), worst-case: Find <math>O(1)</math>, Union: <math>O(n)</math>

Implementierung mit Bäumen:
* ohne Heuristiken: Find <math>O(n)</math>, Union <math>O(n)</math>
* mit Union-By-Size, worst-case: Find <math>O(\log(n))</math>, Union <math>O(1)</math>
* mit Union-By-Size, Pfadkompression, worst-case: Find <math>O(\log(n))</math>, Union <math>O(1)</math>
* mit Union-By-Size, Pfadkompression, Folge von ''m'' Find- und ''n-1'' Union-Operationen: <math>O\left(n + m \cdot\alpha(n)\right)</math>

Dabei ist <math>\alpha(n)</math> die [[Umkehrfunktion]] der [[Ackermannfunktion]] <math>A(n,n)</math>. Sie wächst sehr langsam und ist für alle „praktischen“ Eingaben (<math>n<10^{80}</math>) kleiner als 5. Im Jahr 1977 hat [[Robert Tarjan]] gezeigt, dass für eine Sequenz ''m'' Find- und ''n-1'' Union-Operationen jede Datenstruktur im Pointer-Maschinen Modell eine Laufzeit von <math>\Omega\left(n + m \cdot\alpha(n)\right)</math> benötigt.<ref>{{cite journal |first=Robert E. |last =Tarjan |title = A class of algorithms which require nonlinear time to maintain disjoint sets |language=en |journal = Journal of Computer and System Sciences |volume = 18 |issue = 2 |pages = 110–127 |year = 1979 |doi = 10.1016/0022-0000(79)90042-4}}</ref>
Fredman und Saks haben 1989 gezeigt, dass diese untere Schranke auch im allgemeineren Cell-Probe Modell gilt.<ref>{{Cite conference |first=M. |last=Fredman |first2=M. |last2=Saks |title=The cell probe complexity of dynamic data structures |conference=Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing |pages=345–354 |date=May 1989 |language=en |doi=10.1145/73007.73040}}</ref> Daraus folgt, dass die Datenstruktur mit Union-By-Size und Pfadkompression eine asymptotisch optimale Laufzeit besitzt, und es keine Union-Find-Datenstruktur geben kann, die sowohl ''Find'' als auch ''Union'' [[Amortisierte Analyse|amortisiert]] in O(1) ausführt.

== Anwendungen ==
Union-Find-Strukturen eignen sich gut, um [[Zusammenhang von Graphen|Zusammenhangskomponenten von Graphen]] zu verwalten.

Union-Find-Strukturen können auch genutzt werden, um effizient herauszufinden, ob ein Graph [[Zyklus (Graphentheorie)|Zyklen]] enthält.

Das folgende [[Computerprogramm]] in der [[Programmiersprache]] [[C++]] zeigt die Implementierung eines [[Ungerichteter Graph|ungerichteten Graphen]] mit einem Array von [[Kante (Graphentheorie)|Kanten]]. Der ungerichtete Graph wird als [[Datentyp]] ''UndirectedGraph'' deklariert. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''main'' verwendet, das auf der Konsole ausgibt, ob der gegebene Graph Zyklen enthält. Die [[Funktion (Programmierung)|Funktion]] ''unionSubsets'' verwendet ''union by rank'', um zwei [[Teilmenge]]n von Kanten des Graphen zu vereinigen.<ref>[https://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/ Union-Find Algorithm | Set 2 (Union By Rank and Path Compression)]. In: GeeksforGeeks (englisch)</ref><syntaxhighlight lang="c++">
#include <iostream>
using namespace std;

// Deklariert den Datentyp für die Kanten des Graphen
struct Edge
{
int startIndex, endIndex;
};

// Deklariert den Datentyp für den ungerichteten Graphen
struct UndirectedGraph
{
int numberOfVertices, numberOfEdges;
Edge* edges; // Pointer auf das Array für die Kanten
};

// Deklariert den Datentyp für Teilmengen der Kantenmenge des ungerichteten Graphen
struct subset
{
int parent;
int rank;
};

// Diese Funktion erzeugt einen ungerichteten Graphen
struct UndirectedGraph* createGraph(int numberOfVertices, int numberOfEdges)
{
struct UndirectedGraph* undirectedGraph = new UndirectedGraph();
undirectedGraph->numberOfVertices = numberOfVertices;
undirectedGraph->numberOfEdges = numberOfEdges;
undirectedGraph->edges = new Edge[numberOfEdges];
return undirectedGraph;
}

// Diese rekursive Funktion gibt den Index der Wurzel der Teilmenge mit dem Index i zurück
int find(subset subsets[], int i)
{
// Setzt Index der Wurzel auf den Index der Wurzel der Teilmenge mit dem Index i
if (subsets[i].parent != i)
{
subsets[i].parent = find(subsets, subsets[i].parent); // Rekursiver Aufruf der Funktion
}
return subsets[i].parent;
}

// Diese Methode bildet die Vereinigungsmenge der zwei Teilmengen mit den Indexen index1 und index2
void unionSubsets(subset subsets[], int index1, int index2)
{
int newIndex1 = find(subsets, index1); // Index der Teilmenge mit dem Index index1
int newIndex2 = find(subsets, index2); // Index der Teilmenge mit dem Index index2
// Hängt den Teilbaum mit dem niedrigeren Rang unter die Wurzel des Baums mit dem höheren Rang
if (subsets[newIndex1].rank < subsets[newIndex2].rank)
{
subsets[newIndex1].parent = newIndex2;
}
else if (subsets[newIndex1].rank > subsets[newIndex2].rank)
{
subsets[newIndex2].parent = newIndex1;
}
else // Wenn die Teilbäume denselben Rang haben, wird der Rang des einen Baums erhöht und der andere Baum unter die Wurzel des anderen Baums gehängt
{
subsets[newIndex2].parent = newIndex1;
subsets[newIndex1].rank++;
}
}

// Diese Methode prüft, ob der Graph Zyklen enthält
bool containsCycle(struct UndirectedGraph* graph)
{
int numberOfVertices = graph->numberOfVertices;
int numberOfEdges = graph->numberOfEdges;
Edge* edges = graph->edges; // Pointer auf das Array für die Kanten
subset* subsets = new subset[numberOfVertices]; // Deklariert ein Array für die Teilmengen der Kantenmenge
for (int i = 0; i < numberOfVertices; i++) // for-Schleife, die Teilmengen mit einzelnen Kanten erzeugt
{
subsets[i].parent = i;
subsets[i].rank = 0;
}
for (int i = 0; i < numberOfEdges; i++) // foreach-Schleife, die alle Kanten durchläuft
{
Edge nextEdge = edges[i++]; // Weist die verbleibende Kante mit dem kleinsten Kantengewicht zu und erhöht den Kantenindex für die nächste Iteration um 1
int index1 = find(subsets, nextEdge.startIndex); // Index der Wurzel der Teilmenge mit dem Index nextEdge.startIndex
int index2 = find(subsets, nextEdge.endIndex); // Index der Wurzel der Teilmenge mit dem Index nextEdge.endIndex
if (index1 == index2) // Wenn die Indexe der Wurzeln, also auch die Mengen übereinstimmen, enthält der Graph einen Zyklus
{
return true;
}
unionSubsets(subsets, index1, index2);
}
return false;
}

// Hauptfunktion die das Programm ausführt
int main()
{
int numberOfVertices = 3;
int numberOfEdges = 3;

// Erzeugt den ungerichteten Graphen mit den gegebenen Kanten
struct UndirectedGraph* undirectedGraph = createGraph(numberOfVertices, numberOfEdges);
// Initialisiert das Array mit 3 Kanten
Edge* edges = undirectedGraph->edges;
edges[0].startIndex = 0;
edges[0].endIndex = 1;
edges[1].startIndex = 1;
edges[1].endIndex = 2;
edges[2].startIndex = 0;
edges[2].endIndex = 2;
if (containsCycle(undirectedGraph)) // Aufruf der Methode
{
cout << "Der Graph enthält Zyklen." << endl; // Ausgabe auf der Konsole
}
else
{
cout << "Der Graph enthält keine Zyklen." << endl; // Ausgabe auf der Konsole
}
}
</syntaxhighlight>Der [[Algorithmus von Kruskal]] erfordert beispielsweise eine solche Datenstruktur, um effizient implementiert werden zu können.

== Weblinks ==
* [https://www.cs.usfca.edu/~galles/visualization/DisjointSets.html Demonstration von Union-Find]

== Einzelnachweise ==
<references />

[[Kategorie:Datenstruktur]]
[[Kategorie:Theoretische Informatik]]

Union-Find-Struktur - Versionsgeschichte

imported>Hpod: log -> log_2