Union-Find-Grundlagen
I. Konzept und Einführung
Union-Find ist eine baumförmige Datenstruktur, die zum Zusammenführen und Abfragen einiger disjunkter Mengen verwendet wird.
Die Idee von Union-Find besteht darin, ein Array zu verwenden, um einen gesamten Wald (parent) darzustellen. Der Wurzelknoten eines Baums identifiziert eine Menge eindeutig; solange wir die Baumwurzel eines Elements finden, können wir bestimmen, zu welcher Menge es gehört.
II. Hinweise zur Anwendbarkeit
Union-Find-Mengen werden in einigenNBei Mengenanwendungsproblemen mit Elementen lassen wir üblicherweise jedes Element am Anfang eine einelementige Menge bilden, dann vereinigen wir die Mengen, die Elemente derselben Gruppe enthalten, in einer bestimmten Reihenfolge und finden während des Prozesses wiederholt heraus, zu welcher Menge ein Element gehört. Dieser Prozess mag einfach erscheinen, aber wenn die Datenmenge extrem groß ist, wenn andere Datenstrukturen verwendet werden, um sie zu beschreiben, ist der benötigte Speicherplatz oft zu groß, als dass der Computer ihn bewältigen könnte, und das Ergebnis kann nicht in kurzer Zeit berechnet werden. Daher kann nur die Union-Find-Menge verwendet werden, um damit umzugehen.
III. Grundlegende Datendarstellung der Union-Find-Menge
Wie oben erneut gezeigt0、2、4、6、8Die folgenden sind alle0Diese Menge repräsentiert0、2、4、6、8Diese fünf Elemente sind verbunden,1、3、5、7、9Die folgenden sind alle1Diese Menge repräsentiert0，1、3、5、7、9Diese fünf Elemente sind verbunden.
Erstellen Sie eine Klasse UnionFind, initialisieren Sie sie so, dass jedes id[i] auf sich selbst zeigt, ohne zusammengeführte Elemente:
public UnionFind1(int n) {
count = n;
id = new int[n];
// Initialisierung: Jedes id[i] zeigt auf sich selbst, keine zusammengeführten Elemente
for (int i = 0; i < n; i++)
id[i] = i;
}
...
Java-Beispielcode
Quellcode-Paket-Download:Herunterladen
Code der Datei UnionFind.java:
public class UnionFind{
private int[] id;
// Anzahl der Datenelemente
private int count;
public UnionFind1(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
}
}