Implémentation de l'algorithme de Prim

1. Qu'est-ce qu'un Arbre Couvrant de Poids Minimum ?

Avant de plonger dans l'algorithme, il est essentiel de définir précisément le problème. Un arbre couvrant (Spanning Tree) d'un graphe connexe non orienté est un sous-graphe qui connecte tous les sommets (il est couvrant) et qui ne contient aucun cycle (c'est un arbre). Par conséquent, pour un graphe à $|V|$ sommets, un arbre couvrant aura toujours exactement $|V|-1$ arêtes.

Un graphe peut avoir de nombreux arbres couvrants. Si le graphe est pondéré, chaque arbre couvrant aura un poids total correspondant à la somme des poids de ses arêtes. Le problème de l'arbre couvrant de poids minimum (MST) consiste à trouver un arbre couvrant dont le poids total est le plus faible possible.

Pour vous familiariser avec ces définitions et voir un exemple concret, je vous propose d'explorer la ressource interactive suivante.

Une question naturelle se pose : pourquoi ne pas utiliser un algorithme de plus courts chemins comme Dijkstra ? La raison est subtile : Dijkstra minimise le coût du chemin depuis une source vers chaque autre nœud, alors qu'un MST minimise la somme totale des poids des arêtes de l'arbre lui-même. Les deux objectifs sont différents et conduisent généralement à des arbres différents.

2. Le Principe Fondamental : La Propriété de la Coupe

Les algorithmes de MST les plus connus (Prim et Kruskal) sont des algorithmes gloutons. Leur correction repose sur une propriété fondamentale et très élégante : la propriété de la coupe (ou cut property).

Une coupe est une partition des sommets du graphe en deux ensembles disjoints. Une arête de franchissement (ou crossing edge) est une arête qui relie un sommet d'un ensemble à un sommet de l'autre. La propriété de la coupe énonce que :

Pour n'importe quelle coupe du graphe, l'arête de franchissement de poids minimum appartient à au moins un des arbres couvrants de poids minimum du graphe.

Cette propriété est la pierre angulaire qui justifie le choix glouton. La vidéo suivante l'explique et la démontre de manière très claire.

3. L'Algorithme de Prim

L'algorithme de Prim est une application directe de la propriété de la coupe. Il fonctionne de manière très similaire à Dijkstra :

1. On commence avec un arbre contenant un seul sommet (le sommet de départ).
2. On maintient un ensemble de sommets déjà dans l'arbre en construction.
3. À chaque étape, on applique la propriété de la coupe en considérant la coupe qui sépare les sommets déjà dans l'arbre de ceux qui n'y sont pas encore.
4. On choisit l'arête de poids minimum qui connecte un sommet de l'arbre à un sommet hors de l'arbre.
5. On ajoute cette arête et le nouveau sommet à l'arbre.
6. On répète le processus jusqu'à ce que tous les sommets soient dans l'arbre.

Pour extraire efficacement l'arête de poids minimum à chaque étape, on utilise une file de priorité, tout comme dans l'algorithme de Dijkstra.

La vidéo suivante illustre parfaitement ce processus.

Le document suivant, issu d'un cours de MP2I, formalise l'algorithme avec un pseudo-code rigoureux, très proche de ce qui est attendu en concours.

4. Implémentation en Python

Passons maintenant à l'implémentation, l'objectif principal de cette leçon. Pour implémenter Prim, nous avons besoin de :

1. Une représentation du graphe, typiquement une liste d'adjacence : un dictionnaire où les clés sont les sommets et les valeurs sont des listes de paires (voisin, poids).
2. Une file de priorité (le module heapq de Python est parfait pour cela) pour stocker les arêtes candidates à l'ajout. On y insérera des tuples (poids, sommet, parent).
3. Un ensemble (set) pour garder la trace des sommets déjà inclus dans l'MST, afin d'éviter les cycles et les traitements redondants.

Voici une trame de code que vous pouvez compléter. L'approche est quasiment identique à celle de Dijkstra.

import heapq

def prim(graph, start_vertex):
    """
    Implémente l'algorithme de Prim pour trouver un arbre couvrant de poids minimum.

    Args:
        graph (dict): Le graphe représenté par une liste d'adjacence.
                      Format: {u: [(v, weight), ...], ...}
        start_vertex: Le sommet de départ.

    Returns:
        tuple: Un tuple contenant la liste des arêtes de l'MST et le coût total.
               Format: ([(u, v, weight), ...], total_cost)
    """
    mst_edges = []
    total_cost = 0
    visited = set()
    



    # La file de priorité stockera des tuples (poids, sommet_actuel, parent)
    # Le 'parent' est le sommet de l'arbre auquel 'sommet_actuel' est connecté.
    priority_queue = [(0, start_vertex, None)] # (poids, sommet, parent)
    
    while priority_queue and len(visited) < len(graph):



        # 1. Extraire l'arête de poids minimum connectant l'arbre à un sommet non visité
        weight, current_vertex, parent = heapq.heappop(priority_queue)
        



        # 2. Si le sommet a déjà été visité, on ignore cette arête (elle formerait un cycle)
        if current_vertex in visited:
            continue
            



        # 3. Marquer le sommet comme visité
        visited.add(current_vertex)
        



        # 4. Si ce n'est pas le sommet de départ, ajouter l'arête à l'MST
        if parent is not None:
            mst_edges.append((parent, current_vertex, weight))
            total_cost += weight
            



        # 5. Parcourir les voisins du sommet actuel
        for neighbor, edge_weight in graph.get(current_vertex, []):



            # 6. Si un voisin n'est pas encore dans l'arbre, ajouter l'arête
            #    le reliant à la file de priorité.
            if neighbor not in visited:
                heapq.heappush(priority_queue, (edge_weight, neighbor, current_vertex))
                
    return mst_edges, total_cost




# --- Exemple d'utilisation ---
if __name__ == '__main__':



    # Graphe de l'exemple visuel de la vidéo ByteQuest
    graph = {
        'A': [('B', 2), ('F', 3)],
        'B': [('A', 2), ('D', 2), ('C', 3)],
        'C': [('B', 3), ('D', 1), ('E', 5), ('F', 6)],
        'D': [('B', 2), ('C', 1), ('E', 4)],
        'E': [('C', 5), ('D', 4), ('F', 2)],
        'F': [('A', 3), ('C', 6), ('E', 2)]
    }

    mst, cost = prim(graph, 'A')
    print("Arbre couvrant de poids minimum (arêtes) :", mst)
    print("Coût total :", cost)

Exercice :
Analysez le code ci-dessus, assurez-vous de comprendre chaque étape. Exécutez-le et vérifiez que le résultat correspond à celui de la vidéo "Prim's Algorithm Visually Explained". Essayez de le modifier pour qu'il parte d'un autre sommet (par exemple, 'D') et observez le résultat (le coût total devrait être le même, mais l'arbre peut être différent).

Pour visualiser une étape en détail, l'image suivante décompose l'itération de la boucle principale de Prim.

5. Analyse et Correction

Complexité : L'analyse de complexité est identique à celle de Dijkstra avec un tas binaire. Chaque sommet est ajouté à l'MST une seule fois. Chaque arête (u,v) est considérée au plus deux fois (une fois depuis u, une fois depuis v), entraînant potentiellement une opération heappush. L'opération dominante est l'extraction de la file de priorité (heappop), qui se produit $|V|$ fois. La complexité est donc $O(|E|\log |V|)$.

Preuve de correction : La correction de l'algorithme de Prim découle directement de la propriété de la coupe. À chaque étape, l'algorithme ajoute l'arête la plus légère qui franchit la coupe entre les sommets visités et non visités. Par la propriété de la coupe, cette arête fait partie d'un MST. En procédant ainsi de manière itérative, on construit un MST. Pour une preuve plus formelle par l'absurde, vous pouvez consulter la section "Preuve" du document d'Anthony Lick que nous avons examiné.

Conclusion

Aujourd'hui, nous avons exploré en profondeur l'algorithme de Prim, une solution classique et efficace au problème de l'arbre couvrant de poids minimum.

Les points clés à retenir :

• Un MST connecte tous les sommets d'un graphe pondéré avec le coût total le plus faible possible. C'est un problème différent de celui des plus courts chemins.
• L'algorithme de Prim est une approche gloutonne dont la correction est garantie par la propriété de la coupe.
• Son implémentation est très similaire à celle de Dijkstra, utilisant une file de priorité pour choisir de manière efficace le prochain sommet à ajouter à l'arbre en construction.
• Sa complexité temporelle est de $O(|E|\log |V|)$ avec un tas binaire.

Dans la prochaine leçon, nous poursuivrons notre étude des MST avec l'algorithme de Kruskal. Celui-ci adopte une approche gloutonne différente et nous donnera l'occasion d'étudier une nouvelle structure de données extrêmement puissante et utile : la structure Union-Find.