Union-Find : recherche rapide
Cette section présente les opérations de base basées sur la structure d'union disjointe de la section précédente : requête, union et vérification de la connexion entre éléments.
Interroger l'ID de l'ensemble d'un élément et le renvoyer directement.idValeur du tableau,O(1)complexité temporelle.
...
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
...
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
...
Fusionner les ensembles auxquels appartiennent les élémentspet l'élémentq. Le processus d'union nécessite de parcourir tous les éléments, puis de fusionner les ID d'ensemble des deux éléments. Ce processus est...O(n)Complexité.
...
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
...
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
...
Exemple de code Java
Téléchargement du paquet source :Télécharger
Code du fichier UnionFind1.java :
package example.union;
/**
* Première version de Union-Find
*/
public class UnionFind1 {
// Notre première version de Union-Find est essentiellement un tableau
private int[] id;
// nombre d'éléments de données
private int count;
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;
}
// processus find, trouver le numéro de l'ensemble correspondant à l'élément p
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
// vérifier si l'élément p et l'élément q appartiennent au même ensemble
// complexité O(1)
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
// fusionner les ensembles contenant l'élément p et l'élément q
// complexité O(n)
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
// Le processus de fusion doit parcourir tous les éléments une fois et fusionner les identifiants d'ensemble des deux éléments
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
}
/**
* Première version de Union-Find
*/
public class UnionFind1 {
// Notre première version de Union-Find est essentiellement un tableau
private int[] id;
// nombre d'éléments de données
private int count;
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;
}
// processus find, trouver le numéro de l'ensemble correspondant à l'élément p
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
// vérifier si l'élément p et l'élément q appartiennent au même ensemble
// complexité O(1)
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
// fusionner les ensembles contenant l'élément p et l'élément q
// complexité O(n)
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
// Le processus de fusion doit parcourir tous les éléments une fois et fusionner les identifiants d'ensemble des deux éléments
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
}