algorithm Implémentation optimale, basée sur des ensembles disjoints


Exemple

Nous pouvons faire deux choses pour améliorer les sous-algorithmes simples et sous-optimaux des ensembles disjoints:

  1. Heuristique de compression de chemin : findSet ne doit jamais manipuler un arbre de hauteur supérieure à 2 . S'il finit par itérer un tel arbre, il peut lier directement les nœuds inférieurs à la racine, optimisant ainsi les traversées futures;

    subalgo findSet(v: a node):
        if v.parent != v
            v.parent = findSet(v.parent)
        return v.parent
    
  2. Heuristique de fusion basée sur la hauteur: pour chaque noeud, stockez la hauteur de son sous-arbre. Lors de la fusion, faites du grand arbre le parent du plus petit, ce qui n'augmente pas la hauteur de quiconque.

    subalgo unionSet(u, v: nodes):
        vRoot = findSet(v)
        uRoot = findSet(u)
    
        if vRoot == uRoot:
            return
    
        if vRoot.height < uRoot.height:
            vRoot.parent = uRoot
        else if vRoot.height > uRoot.height:
            uRoot.parent = vRoot
        else:
            uRoot.parent = vRoot
            uRoot.height =  uRoot.height + 1
    

Cela conduit à un temps O(alpha(n)) pour chaque opération, où alpha est l'inverse de la fonction Ackermann à croissance rapide, sa croissance est donc très lente et peut être considérée comme O(1) à des fins pratiques.

Cela rend l’algorithme entier de Kruskal O(m log m + m) = O(m log m) , à cause du tri initial.

Remarque

La compression de chemin peut réduire la hauteur de l’arbre, par conséquent, la comparaison de la hauteur des arbres au cours de l’union peut ne pas être une tâche triviale. Par conséquent, pour éviter la complexité de stocker et de calculer la hauteur des arbres, le parent résultant peut être choisi de manière aléatoire:

    subalgo unionSet(u, v: nodes):
        vRoot = findSet(v)
        uRoot = findSet(u)

        if vRoot == uRoot:
            return
        if random() % 2 == 0:
            vRoot.parent = uRoot
        else:
            uRoot.parent = vRoot

En pratique, cet algorithme randomisé associé à la compression de chemin pour l'opération findSet produira des performances comparables, mais beaucoup plus simples à mettre en œuvre.