algorithm
L'algorithme de Kruskal

Remarques

Implémentation simple et plus détaillée

Afin de gérer efficacement la détection du cycle, nous considérons chaque nœud comme faisant partie d'un arbre. Lors de l'ajout d'une arête, nous vérifions si ses deux nœuds composants font partie d'arbres distincts. Initialement, chaque nœud constitue une arborescence à un nœud.

algorithm kruskalMST'(G: a graph)
    sort G's edges by their value
    MST = a forest of trees, initially each tree is a node in the graph
    for each edge e in G:
        if the root of the tree that e.first belongs to is not the same 
        as the root of the tree that e.second belongs to:
            connect one of the roots to the other, thus merging two trees
    
    return MST, which now a single-tree forest

Implémentation simple, basée sur des ensembles disjoints

La méthodologie forestière ci-dessus est en réalité une structure de données disjointe, qui implique trois opérations principales:

subalgo makeSet(v: a node):
    v.parent = v    <- make a new tree rooted at v
    

subalgo findSet(v: a node):
    if v.parent == v:
        return v
    return findSet(v.parent)

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

    uRoot.parent = vRoot

algorithm kruskalMST''(G: a graph):
    sort G's edges by their value
    for each node n in G:
        makeSet(n)
    for each edge e in G:
        if findSet(e.first) != findSet(e.second):
            unionSet(e.first, e.second)

Cette implémentation naïve conduit à un temps O(n log n) pour gérer la structure de données de l'ensemble disjoint, conduisant à l'heure O(m*n log n) pour tout l'algorithme de Kruskal.

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

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.

Implémentation simple et de haut niveau

Triez les arêtes par valeur et ajoutez-en chacune au MST dans l'ordre trié, si cela ne crée pas de cycle.

algorithm kruskalMST(G: a graph)
    sort G's edges by their value
    MST = an empty graph
    for each edge e in G:
        if adding e to MST does not create a cycle:
            add e to MST

    return MST