Kruskal

Principe

L'objectif de l'algorithme de Kruskal est de construire l'arbre couvrant minimal d'un graphe (cf. l'article sur les arbres couvrants minimaux) Son approche est fondée sur deux algorithmes essentiels :

Tri (rapide) en O(n log n).
Union-Find

L'idée est de gloutonner sur la liste des arcs triée par pondérations croissantes. On considère les arcs au fur et à mesure tout en maintenant en permanence des ensembles de noeuds disjoints : on ajoute un arc à l'arbre si et seulement si il relie deux noeuds de composantes différentes.

Pseudo code

Fonction Kruskal(Graphe G)
    Soit A la liste des arcs de G
    Soit T = [] (liste vide)
 
    Trier les arcs de A par poids croissant
 
    Pour chaque arc a = (noeudA, noeudB, poids) de A
        Si composante(noeudA) != composante(noeudB)
            Ajouter a à la liste T
            unifier(noeudA, noeudB)
 
    Retourner T

Vérifier le résultat

Par définition, si N est le nombre de noeuds du graphe G alors le nombre d'arcs de l'arbre couvrant est N - 1. Une procédure de vérification est donc triviale à mettre en place.