Principes de base d'Union-Find
I. Concept et introduction
L'Union-Find est une structure de données en forme d'arbre utilisée pour gérer la fusion et l'interrogation de certains ensembles disjoints.
L'idée de l'Union-Find est d'utiliser un tableau pour représenter une forêt entière (parent). Le nœud racine d'un arbre identifie de manière unique un ensemble ; tant que nous trouvons la racine de l'arbre d'un élément, nous pouvons déterminer à quel ensemble il appartient.
II. Notes d'applicabilité
Les ensembles Union-Find sont utilisés dans certainsNDans les problèmes d'application d'ensembles avec des éléments, nous laissons généralement chaque élément former un ensemble singleton au début, puis nous fusionnons les ensembles contenant des éléments du même groupe dans un certain ordre, et nous trouvons de manière répétée à quel ensemble un élément appartient pendant le processus. Ce processus peut sembler simple, mais lorsque la quantité de données est extrêmement grande, si d'autres structures de données sont utilisées pour le décrire, l'espace requis est souvent trop grand pour que l'ordinateur puisse le supporter, et le résultat ne peut pas être calculé en peu de temps. Par conséquent, seul l'ensemble union-find peut être utilisé pour le gérer.
III. Représentation de base des données de l'ensemble Union-Find
Encore comme montré ci-dessus0、2、4、6、8Les suivants sont tous0Cet ensemble représente0、2、4、6、8Ces cinq éléments sont connectés,1、3、5、7、9Les suivants sont tous1Cet ensemble représente0，1、3、5、7、9Ces cinq éléments sont connectés.
Construisez une classe UnionFind, initialisez-la de sorte que chaque id[i] pointe vers lui-même, sans éléments fusionnés :
public UnionFind1(int n) {
count = n;
id = new int[n];
// Initialisation : chaque id[i] pointe vers lui-même, aucun élément fusionné
for (int i = 0; i < n; i++)
id[i] = i;
}
...
Exemple de code Java
Téléchargement du paquet de code source :Télécharger
Code du fichier UnionFind.java :
public class UnionFind{
private int[] id;
// nombre d'éléments de données
private int count;
public UnionFind1(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
}
}