Algorithme de Prim en Python : arbre couvrant minimum avec heapq

L’algorithme de Prim relie les sommets d’un graphe pondéré non orienté avec un coût total minimal, sans cycle. Le résultat est un arbre couvrant minimum lorsque le graphe est connexe. Si plusieurs composantes sont séparées, il faut une forêt : un arbre par composante.

Cette implémentation Python utilise heapq, gère les égalités de poids sans comparer les noms des sommets et distingue explicitement arbre et forêt. Le code complet et ses six tests fonctionnent avec la bibliothèque standard de Python 3.12.

Arbre couvrant minimum ou plus court chemin ?

Prim minimise la somme des arêtes d’un réseau qui relie tous les sommets. Il ne minimise pas le trajet entre deux sommets particuliers. Un réseau de câbles de coût minimal et un itinéraire de coût minimal sont deux problèmes différents.

À chaque étape, Prim choisit une arête de poids minimal qui traverse la frontière entre les sommets déjà atteints et les autres. La présentation de Princeton sur les arbres couvrants minimum explique la propriété de coupe qui justifie ce choix glouton. Des poids négatifs sont permis ; en cas d’égalité, plusieurs arbres minimaux peuvent exister.

Représenter et contrôler le graphe

Le dictionnaire associe chaque sommet à une liste de couples (voisin, poids). Chaque arête non orientée doit apparaître dans les deux sens, avec le même poids. Les sommets isolés doivent aussi être des clés avec une liste vide.

Le validateur du script refuse un voisin absent, une arête asymétrique, un poids qui n’est ni un entier ni un flottant Python, ainsi que NaN et les infinis. Les arêtes parallèles sont autorisées si leurs multiplicités sont symétriques. Les boucles sont ignorées par la recherche : elles ne relient pas un nouveau sommet.

Les sommets doivent être hachables. Ils peuvent être de types différents, y compris None, sans devoir être comparables entre eux. Comme pour tout dictionnaire Python, deux valeurs égales et de même hash représentent la même clé ; 1 et True ne désignent donc pas deux sommets distincts.

Pourquoi ajouter un numéro dans heapq ?

Un tas de tuples compare d’abord les poids, puis les éléments suivants en cas d’égalité. Une entrée (poids, sommet, parent) peut échouer si deux poids égaux conduisent à comparer un entier et une chaîne.

Nous utilisons (poids, numéro, sommet, parent). Le compteur unique départage les entrées avant les noms des sommets. C’est le principe présenté dans les notes officielles sur les files de priorité. Une sentinelle privée représente la racine ; elle permet de conserver None comme sommet valide.

Implémentation complète : arbre et forêt

Enregistrez ce bloc dans prim_foret.py et lancez python prim_foret.py. La fonction prim exige un départ présent et un graphe connexe. foret_prim traite toutes les composantes, même les sommets isolés. Le graphe vide donne une forêt vide de coût zéro.

"""Prim paresseux : graphe non orienté, poids réels finis, sommets hachables."""
from collections import Counter
from heapq import heappop, heappush
from itertools import count
from math import isfinite

def valider(graphe):
    aretes = Counter()
    for u, voisins in graphe.items():
        for v, poids in voisins:
            if v not in graphe:
                raise ValueError("Voisin absent des clés du graphe")
            if type(poids) not in (int, float) or (type(poids) is float and not isfinite(poids)):
                raise ValueError("Poids entier ou flottant fini attendu")
            aretes[u, v, poids] += 1
    for (u, v, poids), nombre in aretes.items():
        if aretes[v, u, poids] != nombre:
            raise ValueError("Chaque arête doit apparaître dans les deux sens")

def _composante(graphe, depart, visites):
    numero = count()
    racine = object()  # None peut lui-même être un sommet valide.
    file = [(0, next(numero), depart, racine)]
    arbre, sommets, cout = [], set(), 0
    while file:
        poids, _, u, parent = heappop(file)
        if u in visites:
            continue
        visites.add(u)
        sommets.add(u)
        if parent is not racine:
            arbre.append((parent, u, poids))
            cout += poids
        for v, w in graphe[u]:
            if v not in visites:
                # Le numéro unique départage les poids sans comparer les sommets.
                heappush(file, (w, next(numero), v, u))
    return cout, arbre, sommets

def prim(graphe, depart):
    valider(graphe)
    if depart not in graphe:
        raise ValueError("Le sommet de départ n'existe pas")
    cout, arbre, sommets = _composante(graphe, depart, set())
    if len(sommets) != len(graphe):
        raise ValueError("Le graphe n'est pas connexe : utiliser foret_prim")
    return cout, arbre

def foret_prim(graphe):
    valider(graphe)
    visites, composantes, total = set(), [], 0
    for depart in graphe:
        if depart not in visites:
            cout, arbre, sommets = _composante(graphe, depart, visites)
            total += cout
            composantes.append({'sommets': sommets, 'aretes': arbre, 'cout': cout})
    return total, composantes

if __name__ == '__main__':
    graphe = {
        'A': [('B', 4), ('C', 2)],
        'B': [('A', 4), ('C', 1), ('D', 5)],
        'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],
        'D': [('B', 5), ('C', 8), ('E', 2), ('F', 6)],
        'E': [('C', 10), ('D', 2), ('F', 3)],
        'F': [('D', 6), ('E', 3)],
    }
    print('Arbre connexe :', prim(graphe, 'A'))
    non_connexe = {'A': [('B', 1)], 'B': [('A', 1)],
                   'C': [('D', 2)], 'D': [('C', 2)], 'I': []}
    try:
        prim(non_connexe, 'A')
    except ValueError as erreur:
        print(erreur)
    total, composantes = foret_prim(non_connexe)
    print('Forêt : coût', total, 'composantes', len(composantes))
    print('Sommets par composante :', [sorted(c['sommets']) for c in composantes])

Résultat exécuté et graphe non connexe

Arbre connexe : (13, [('A', 'C', 2), ('C', 'B', 1), ('B', 'D', 5), ('D', 'E', 2), ('E', 'F', 3)])
Le graphe n'est pas connexe : utiliser foret_prim
Forêt : coût 3 composantes 3
Sommets par composante : [['A', 'B'], ['C', 'D'], ['I']]

Le graphe connexe contient six sommets. L’arbre sélectionne cinq arêtes et coûte 13 : A–C (2), C–B (1), B–D (5), D–E (2), E–F (3). Ces deux premiers contrôles sont utiles, mais compter cinq arêtes ne suffit pas à prouver que l’arbre est minimal.

Le second graphe contient A–B, C–D et un sommet I isolé. L’appel à prim lève une erreur au lieu de présenter la première composante comme un arbre couvrant complet. La forêt contient trois composantes, deux arêtes et coûte 3. Chaque composante expose ses sommets, ses arêtes et son coût ; le sommet isolé reste donc visible dans le résultat.

Une forêt couvrante d’un graphe à V sommets et C composantes contient V − C arêtes. En cas de poids égaux, la liste exacte peut changer selon l’ordre des données, tout en gardant le même coût minimal.

Six tests, dont un calcul indépendant du minimum

Placez le bloc suivant dans test_prim.py, à côté du script, puis lancez python test_prim.py. Le test indépendant énumère les sous-ensembles de quatre arêtes de petits graphes à cinq sommets, conserve ceux qui les relient tous et prend le coût minimal. Il compare ce minimum à Prim depuis chacun des cinq départs, sur quinze graphes déterministes avec des poids négatifs et des égalités.

from itertools import combinations
import random,unittest
from prim_foret import prim,foret_prim

def graphe(n,aretes):
    g={i:[] for i in range(n)}
    for u,v,w in aretes:g[u].append((v,w));g[v].append((u,w))
    return g

def cout_exhaustif(n,aretes):
    candidats=[]
    for choix in combinations(aretes,n-1):
        g=graphe(n,choix);vus={0};pile=[0]
        while pile:
            for v,_ in g[pile.pop()]:
                if v not in vus:vus.add(v);pile.append(v)
        if len(vus)==n:candidats.append(sum(w for _,_,w in choix))
    return min(candidats)

class PrimTests(unittest.TestCase):
    def test_minimum_independant(self):
        rng=random.Random(42)
        for _ in range(15):
            aretes=[(u,v,rng.randrange(-3,7)) for u,v in combinations(range(5),2)]
            attendu=cout_exhaustif(5,aretes)
            for depart in range(5):
                cout,arbre=prim(graphe(5,aretes),depart)
                self.assertEqual(cout,attendu);self.assertEqual(len(arbre),4)
    def test_non_connexe_et_isole(self):
        g=graphe(5,[(0,1,1),(2,3,2)])
        with self.assertRaises(ValueError):prim(g,0)
        cout,cs=foret_prim(g);self.assertEqual((cout,len(cs)),(3,3))
        self.assertEqual(set.union(*(c['sommets'] for c in cs)),set(g))
        self.assertEqual([len(c['aretes']) for c in cs],[1,1,0])
    def test_sommets_non_comparables(self):
        g={None:[('A',1),(3,1)],'A':[(None,1)],3:[(None,1)]}
        cout,a=prim(g,None);self.assertEqual((cout,len(a)),(2,2))
    def test_vide_et_singleton(self):
        self.assertEqual(foret_prim({}),(0,[]))
        self.assertEqual(prim({'A':[]},'A'),(0,[]))
        with self.assertRaises(ValueError):prim({},'A')
    def test_graphe_invalide(self):
        for g in [{'A':[('B',1)]},{'A':[('B',1)],'B':[]},
                  {'A':[('A',float('nan'))]},{'A':[('A',float('inf'))]}]:
            with self.assertRaises(ValueError):foret_prim(g)
    def test_aretes_paralleles_et_boucle(self):
        g=graphe(2,[(0,1,4),(0,1,-1)]);g[0].append((0,-10))
        self.assertEqual(prim(g,0)[0],-1)

if __name__=='__main__':unittest.main(verbosity=2)

Les six tests passent. Les autres cas couvrent la forêt avec un sommet isolé, des noms non comparables, le graphe vide, les entrées invalides, les arêtes parallèles et une boucle négative. L’énumération exhaustive reste réservée aux petits graphes : elle sert de référence de test, pas de méthode efficace pour vos données.

Coût de cette implémentation

Il s’agit d’une version paresseuse de Prim : plusieurs arêtes candidates peuvent viser le même sommet. Une entrée devenue inutile est ignorée lorsqu’elle sort du tas. Le tas peut contenir O(E) entrées.

Pour le parcours de toutes les composantes, la borne de temps est O(V + E log(E + 1)) et la mémoire auxiliaire O(V + E), en comptant validation, visites, tas et résultat. Ces bornes supposent des opérations usuelles à coût constant sur les poids et les clés. Elles restent pertinentes pour un graphe avec de nombreux sommets isolés ; écrire seulement O(E log E) masquerait leur traitement.

Une file indexée avec mise à jour des priorités donne une autre organisation de Prim. Pour un graphe simple connexe, log E et log V sont du même ordre ; préciser l’implémentation aide à comprendre la mémoire et les doublons du tas. Voir le guide de complexité.

Quand choisir Prim ou une bibliothèque de graphes ?

Prim convient bien à une liste d’adjacence. Kruskal part plutôt d’une liste d’arêtes triées et évite les cycles avec une structure Union-Find. Les deux résolvent le même problème non orienté ; consultez la comparaison Prim et Kruskal pour choisir une représentation.

Pour un projet qui utilise déjà NetworkX, sa fonction minimum_spanning_tree propose notamment Prim et renvoie une forêt si le graphe n’est pas connexe. Le contrat d’entrée reste à contrôler ; notre validateur pédagogique n’est pas un lecteur universel de formats de graphes.

Exercices et suite

1. Ajoutez un septième sommet isolé au premier exemple : prim doit échouer et foret_prim garder un coût de 13 avec deux composantes.
2. Remplacez les noms par des objets hachables non comparables et créez des égalités de poids. Le compteur doit empêcher toute comparaison de noms.
3. Changez une seule des deux copies d’une arête : le validateur doit refuser le graphe avant le calcul.

Continuez avec le parcours des algorithmes de graphes. Si votre besoin porte sur un graphe orienté ou sur des trajets, formulez ce problème séparément avant de choisir un algorithme.