Compression de chemin Union-Find
Dans la fonction find de l'union d'ensembles disjoints, une compression de chemin peut être effectuée pour trouver plus rapidement le nœud racine d'un nœud. Pour un arbre d'ensemble, de nombreux nœuds peuvent être attachés sous son nœud racine. Par conséquent, pendant le processus de find, nous pouvons essayer de déplacer le nœud vers le haut autant que possible de bas en haut si le nœud actuellement visité n'est pas le nœud racine, réduisant ainsi la profondeur de l'arbre. Ce processus est appelé compression de chemin.
Comme le montre la figure ci-dessous, le processus de find(4) peut utiliser la compression de chemin pour réduire le nombre de niveaux dans l'arbre.
Lorsque le nœud 4 recherche vers le haut le nœud racine, la première étape de compression réduit d'un le nombre de niveaux de l'arbre :
Le nœud 2 recherche également vers le haut et n'est pas le nœud racine, donc pointez l'élément 2 vers le parent de son nœud parent d'origine. Après cette opération, le nombre de niveaux de l'arbre est réduit d'un en conséquence, et le nœud racine 0 est renvoyé.
Modifiez le code du processus find pour :
// complexité O(h), h est la hauteur de l'arbre
private int find(int p){
assert( p >= 0 && p < count );
// compression de chemin 1
while( p != parent[p] ){
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
La compression de chemin décrite ci-dessus n'est pas l'approche optimale. Nous pouvons compresser l'arbre d'origine sous la forme illustrée dans la figure ci-dessous, qui possède le nombre minimal de niveaux.
Ce processus find peut être représenté comme :
// processus find, trouver le numéro de l'ensemble correspondant à l'élément p
// complexité O(h), h est la hauteur de l'arbre
private int find(int p) {
assert (p >= 0 && p < count);
// Deuxième algorithme de compression de chemin
if (p != parent[p])
parent[p] = find(parent[p]);
return parent[p];
}
...
Exemple de code Java
Téléchargement du paquet de code source :Télécharger
Code du fichier UnionFind3.java :
/**
* Optimisation basée sur le rang
*/
public class UnionFind4 {
private int[] rank; // rank[i] représente le nombre de niveaux de l'arbre représenté par l'ensemble ayant pour racine i
private int[] parent; // parent[i] représente le nœud parent vers lequel pointe le i-ème élément
private int count; // nombre d'éléments de données
// constructeur
public UnionFind4(int count){
rank = new int[count];
parent = new int[count];
this.count = count;
// initialisation, chaque parent[i] pointe vers lui-même, indiquant que chaque élément forme un ensemble à lui seul
for( int i = 0 ; i < count ; i ++ ){
parent[i] = i;
rank[i] = 1;
}
}
// processus find, trouver le numéro de l'ensemble correspondant à l'élément p
// complexité O(h), h est la hauteur de l'arbre
private int find(int p){
assert( p >= 0 && p < count );
// continuer à interroger le nœud parent jusqu'à atteindre le nœud racine
// caractéristique du nœud racine : parent[p] == p
while( p != parent[p] )
p = parent[p];
return p;
// Deuxième algorithme de compression de chemin
//if( p != parent[p] )
//parent[p] = find( parent[p] );
//return parent[p];
}
// vérifier si l'élément p et l'élément q appartiennent au même ensemble
// complexité O(h), h est la hauteur de l'arbre
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(h), h est la hauteur de l'arbre
public void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if( pRoot == qRoot )
return;
if( rank[pRoot] < rank[qRoot] ){
parent[pRoot] = qRoot;
}
else if( rank[qRoot] < rank[pRoot]){
parent[qRoot] = pRoot;
}
else{ // rank[pRoot] == rank[qRoot]
parent[pRoot] = qRoot;
rank[qRoot] += 1; // maintenir la valeur de rank
}
}
}