Union-Find Quick Union

Pour un ensemble de données, la structure de données Union-Find prend principalement en charge deux opérations :

  • union(p,q) - Relier les deux éléments p et q ensemble.

  • find(p)- Interroger l'ensemble auquel appartient l'élément p.

  • isConnected(p,q)- Vérifier si les deux éléments p et q sont connectés.

Dans la sous-section précédente, nous avons utiliséidpour représenter l'ensemble Union-Find sous forme de tableau ; la complexité temporelle de l'opération find en utilisation réelle estO(1), mais l'efficacité de connexion n'était pas élevée.

Dans cette sous-section, nous allons implémenter l'ensemble Union-Find d'une autre manière. Considérer chaque élément comme un nœud qui pointe vers son nœud parent, et le nœud racine pointe vers lui-même. Comme le montre la figure ci-dessous, le nœud 3 pointe vers le nœud 2, ce qui signifie que 3 et 2 sont connectés ; le nœud 2 est lui-même le nœud racine, donc il pointe vers lui-même.

Nous utilisons aussi un tableau pour représenter l'ensemble Union-Find, mais le groupe d'éléments suivant utiliseparentpour représenter le nœud parent vers lequel l'élément courant pointe. Chaque élément pointe vers lui-même, et tous sont indépendants.

Si l'on effectue à ce momentunion(4,3), faire pointer l'élément 4 vers l'élément 3 :

Le tableau change également en conséquence :

Pour déterminer si deux éléments sont connectés, il suffit de vérifier si leurs nœuds racines sont identiques.

Comme le montre la figure ci-dessous, les nœuds racines des nœuds 4 et 9 sont tous les deux 8, donc ils sont connectés.

Pour connecter deux éléments, il suffit de trouver leurs nœuds racines correspondants et de connecter les nœuds racines ; ils deviennent alors des nœuds connectés.

Supposons que nous voulions connecter 6 et 4 dans la figure ci-dessus ; nous avons seulement besoin de faire pointer le nœud racine 5 de 6 vers le nœud racine 8 de 4.

Pour construire une telle structure arborescente pointant vers les nœuds parents, utilisez un tableau pour construire un arbre pointant vers les nœuds parents ; parent[i] représente le nœud parent vers lequel pointe l'élément i.

...
private int[] parent;
private int count;  // nombre d'éléments de données
...

Processus de recherche : pour trouver le numéro d'ensemble correspondant à l'élément p, interrogez continuellement son nœud parent jusqu'à atteindre le nœud racine. Le nœud racine est caractérisé par parent[p] == p, avec une complexité O(h), où h est la hauteur de l'arbre.

...
private int find(int p){
    assert( p >= 0 && p < count );
    while( p != parent[p] )
        p = parent[p];
    return p;
}
...

Pour fusionner les ensembles auxquels appartiennent l'élément p et l'élément q, trouvez respectivement les nœuds racines des deux éléments, et faites pointer un nœud racine vers l'autre nœud racine ; alors les deux ensembles sont fusionnés. Cette opération a une complexité temporelle O(h), où 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;
    parent[pRoot] = qRoot;
}

Exemple de code Java

Téléchargement du paquet de code source :Télécharger

Code du fichier UnionFind2.java :

package example.union;
/**
* Deuxième version de UnionFind
 */
public class UnionFind2 {
    // Notre deuxième version de Union-Find utilise un tableau pour construire un arbre pointant vers les nœuds parents
    // parent[i] représente le nœud parent du i-ème élément
    private int[] parent;
    private int count;  // nombre d'éléments de données
    // constructeur
    public UnionFind2(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;
    }
    // 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;
    }
    // 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;
        parent[pRoot] = qRoot;
    }
}
autres extensions