Algorithme de Kruskal avec Union-Find

1. La Stratégie Gloutonne de Kruskal

L'idée fondamentale de Joseph Kruskal est d'une grande simplicité. Pour construire un MST, il suffit de suivre une règle gloutonne très intuitive :

1. On trie toutes les arêtes du graphe par poids croissant.
2. On parcourt les arêtes dans cet ordre. Pour chaque arête, on l'ajoute à notre futur arbre couvrant à la seule condition qu'elle ne forme pas un cycle avec les arêtes déjà sélectionnées.
3. On s'arrête lorsque l'arbre contient $V-1$ arêtes, où $V$ est le nombre de sommets.

Au début, notre "arbre" est en réalité une "forêt" de $V$ arbres, où chaque arbre est un sommet isolé. Chaque fois que nous ajoutons une arête (u, v), nous fusionnons les deux arbres (ou composantes connexes) qui contenaient u et v. La condition "ne pas former de cycle" se traduit alors très simplement : l'arête (u, v) est valide si et seulement si u et v n'appartiennent pas déjà à la même composante.

C'est précisément le problème que la structure Union-Find résout. Les composantes de notre forêt sont les ensembles disjoints.

• Vérifier si u et v sont dans la même composante se fait avec find(u) == find(v).
• Fusionner les deux composantes se fait avec union(u, v).

Pour une première visualisation de ce processus, je vous invite à regarder le début de la vidéo suivante.

L'image ci-dessous illustre un état intermédiaire de l'algorithme. Les ensembles disjoints gérés par la structure Union-Find correspondent aux composantes connexes en cours de construction.

2. Formalisation de l'Algorithme

Formalisons maintenant l'algorithme. Le document suivant, issu d'un mémoire de maîtrise, présente le pseudo-code de manière rigoureuse, ce qui est le niveau de formalisme attendu pour vos épreuves.

En résumé, le pseudo-code de l'algorithme de Kruskal est le suivant :

Fonction KRUSKAL(G = (V, E, w)) :

1. MST = {} (ensemble vide pour les arêtes de l'arbre final)
2. uf = initialiser_UnionFind(V) (chaque sommet est dans son propre ensemble)
3. Trier les arêtes E dans une liste L par poids w croissant.
4. Pour chaque arête (u, v) de L :

5.  Si `uf.find(u) != uf.find(v)` :
   

6.      Ajouter l'arête `(u, v)` à `MST`.
   

7.      `uf.union(u, v)`.
   

8. Retourner MST.

Ce pseudo-code a l'avantage de montrer l'interaction directe et essentielle entre l'algorithme principal et la structure de données Union-Find.

3. Implémentation en Python

Nous allons maintenant implémenter la fonction kruskal. Vous réutiliserez la classe UnionFind que nous avons développée lors de la leçon précédente.

Le principal travail consiste à écrire la fonction kruskal qui orchestre les opérations : tri des arêtes et boucle de décision utilisant find et union.

Pour vous guider, la vidéo de ByteQuest que nous avons vue précédemment propose une implémentation Python très claire.

Exercice d'implémentation

Reprenez votre classe UnionFind et écrivez la fonction kruskal. Supposez que le graphe est donné sous la forme d'un nombre de sommets V et d'une liste d'arêtes, où chaque arête est un tuple (u, v, poids).

# Collez ici votre classe UnionFind de la leçon précédente.
class UnionFind:
    """
    Implémentation de la structure de données Union-Find avec union par rang
    et compression de chemins.
    """
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            if self.rank[root_i] < self.rank[root_j]:
                self.parent[root_i] = root_j
            elif self.rank[root_i] > self.rank[root_j]:
                self.parent[root_j] = root_i
            else:
                self.parent[root_j] = root_i
                self.rank[root_i] += 1
            return True
        return False




# --- À vous de compléter ---
def kruskal(V, edges):
    """
    Calcule l'arbre couvrant de poids minimum d'un graphe avec l'algorithme de Kruskal.

    Args:
        V (int): Le nombre de sommets dans le graphe (numérotés de 0 à V-1).
        edges (list): Une liste de tuples (u, v, poids) représentant les arêtes.

    Returns:
        list: Une liste d'arêtes (u, v, poids) formant le MST.
        int: Le poids total du MST.
    """
    mst = []
    mst_weight = 0
    



    # 1. Trier les arêtes par poids croissant.
    # La fonction sorted() avec une clé lambda est parfaite pour cela.
    sorted_edges = sorted(edges, key=lambda item: item[2])
    



    # 2. Initialiser la structure Union-Find.
    uf = UnionFind(V)
    
    num_edges = 0



    # 3. Itérer sur les arêtes triées.
    for u, v, weight in sorted_edges:



        # 4. Si les sommets de l'arête ne sont pas déjà dans le même ensemble...
        if uf.find(u) != uf.find(v):



            # ...alors l'arête ne forme pas de cycle.
            # 5. On fusionne les ensembles et on ajoute l'arête au MST.
            uf.union(u, v)
            mst.append((u, v, weight))
            mst_weight += weight
            num_edges += 1
            



            # Optimisation : arrêter quand on a V-1 arêtes.
            if num_edges == V - 1:
                break
                
    return mst, mst_weight




# --- Exemple d'utilisation ---
if __name__ == '__main__':
    V = 4
    edges = [
        (0, 1, 10),
        (0, 2, 6),
        (0, 3, 5),
        (1, 3, 15),
        (2, 3, 4)
    ]

    minimum_spanning_tree, total_weight = kruskal(V, edges)
    print("Arêtes du MST:", minimum_spanning_tree) # Devrait être [(2, 3, 4), (0, 3, 5), (0, 1, 10)]
    print("Poids total:", total_weight)            # Devrait être 19

Prenez le temps d'étudier la solution proposée. Elle traduit fidèlement le pseudo-code et intègre une optimisation simple mais efficace : l'algorithme s'arrête dès que $V-1$ arêtes ont été ajoutées à l'arbre, car nous savons qu'un arbre couvrant sur $V$ sommets a exactement $V-1$ arêtes.

4. Analyse de Complexité et Conclusion

L'analyse de complexité de l'algorithme de Kruskal est un point essentiel.

1. Tri des arêtes : Avec un algorithme de tri efficace (comme le tri fusion ou le tri rapide en cas moyen), cette étape prend $O(E\log E)$ où $E$ est le nombre d'arêtes.
2. Initialisation de Union-Find : Cette étape prend $O(V)$ où $V$ est le nombre de sommets.
3. Boucle sur les arêtes : Dans le pire des cas, nous parcourons toutes les $E$ arêtes. À l'intérieur de la boucle, nous effectuons deux opérations find et une opération union. Grâce à nos optimisations, le coût amorti de ces opérations est $O(\alpha (V))$, où $\alpha$ est la fonction inverse d'Ackermann, une fonction à croissance extrêmement lente. Le coût total de la boucle est donc proche de $O(E\cdot \alpha (V))$.

La complexité totale est donc $O(E\log E+E\cdot \alpha (V))$. Comme $\log E$ croît plus vite que $\alpha (V)$, la complexité de l'algorithme de Kruskal est dominée par le tri des arêtes : $O(E\log E)$.

Points clés à retenir :

• L'algorithme de Kruskal est une approche gloutonne globale qui sélectionne les arêtes les moins chères en premier.
• Sa pièce maîtresse est l'utilisation de Union-Find pour détecter les cycles en temps quasi constant.
• Sa complexité est de $O(E\log E)$, déterminée par l'étape de tri initiale.
• Il est particulièrement efficace pour les graphes clairsemés (où $E$ est proche de $V$) et lorsque les arêtes peuvent être facilement triées.

Félicitations, vous maîtrisez désormais les deux grands algorithmes classiques pour le calcul des arbres couvrants de poids minimum : Prim et Kruskal.

Dans notre prochaine leçon, nous ferons un retour sur l'algorithme de Dijkstra. Nous ne l'implémenterons pas de nouveau, mais nous nous attèlerons à une tâche fondamentale pour l'agrégation : prouver formellement sa correction en utilisant un raisonnement par récurrence, ce qui mobilisera les compétences acquises dans les tout premiers modules.