L'algorithme de Prim expliqué

Mohammed Islam Hadjoudj

Ingénieur expert en recherche opérationnelle

1. Introduction à l'algorithme de Prim

L'algorithme de Prim construit un arbre couvrant de poids minimal : pour un graphe connexe, non orienté et pondéré, il sélectionne un sous-ensemble d'arêtes qui touche tous les sommets, ne contient aucun cycle et possède le plus petit poids total possible. Dans un graphe à V sommets, ce sous-ensemble contient toujours exactement V - 1 arêtes.

La stratégie consiste à faire croître un unique arbre vers l'extérieur. Partez d'un sommet quelconque, puis franchissez à répétition la frontière de ce que vous avez déjà bâti pour ramener l'arête la moins chère qui touche un sommet que vous ne possédez pas encore. Répétez V - 1 fois et l'arbre est terminé. Il n'y a pas de retour en arrière et rien n'est jamais retiré.

Cette description semble presque trop gloutonne pour être correcte. Choisir l'arête la moins chère disponible sur l'instant, sans anticipation, est exactement la stratégie qui échoue pour les plus courts chemins dès qu'une arête négative apparaît. Pour les arbres couvrants de poids minimal elle n'échoue pas, et la raison tient en un seul théorème qu'il vaut mieux comprendre avant de toucher au code.

2. Pourquoi cela fonctionne : la propriété de coupe

Une coupe partage les sommets en deux groupes non vides. Une arête traverse la coupe si ses deux extrémités tombent dans des groupes différents. Le théorème qui fonde l'algorithme de Prim est le suivant :

La preuve est courte et mérite d'être vue, car elle explique tout l'algorithme. Soit e l'arête la moins chère traversant une coupe, et supposons qu'un arbre couvrant de poids minimal T ne la contienne pas. Ajouter e à T crée exactement un cycle, et ce cycle doit traverser la coupe une seconde fois, par une autre arête f. Retirez f. Vous avez toujours un arbre couvrant et, comme e était l'arête traversante la moins chère, son poids n'excède pas celui de f, si bien que le nouvel arbre n'est pas plus lourd. Il existe donc un arbre couvrant de poids minimal contenant e.

Regardez maintenant ce que fait l'algorithme de Prim à chaque étape. Les sommets déjà dans l'arbre forment un côté d'une coupe, et tout le reste forme l'autre. L'algorithme sélectionne l'arête la moins chère traversant précisément cette coupe. Par la propriété de coupe, chaque arête qu'il retient est sûre : elle appartient à un arbre couvrant de poids minimal. Le choix glouton n'est jamais un pari qui se trouve payant, c'est un théorème appliqué V - 1 fois.

3. Comment l'arbre grandit

Concrètement, l'algorithme maintient trois choses : l'ensemble des sommets déjà dans l'arbre, une valeur key pour chaque sommet à l'extérieur, et un pointeur parent retenant quel sommet de l'arbre a offert cette clé.

• key[v] est le poids de l'arête unique la moins chère reliant v à l'arbre courant, ou l'infini si une telle arête n'existe pas encore.
• parent[v] est le sommet de l'arbre à l'autre bout de cette arête. C'est ce qui permet de restituer à la fin l'arbre lui-même et pas seulement son poids.

Chaque tour prend le sommet hors de l'arbre dont la key est la plus petite, l'ajoute avec l'arête vers son parent, puis relâche : pour chaque voisin w encore hors de l'arbre, si l'arête vers w est moins chère que key[w], abaissez key[w] et redirigez parent[w].

Notez bien ce que représente la clé. C'est le poids d'une seule arête, pas le coût d'un chemin. Ce détail unique est ce qui sépare cet algorithme de celui de Dijkstra, un point sur lequel il faudra revenir une fois le code posé.

4. Exécution pas à pas

Prenons le graphe à six sommets utilisé tout au long de notre guide des arbres couvrants de poids minimal. Ses neuf arêtes sont :

A-B 4    A-C 1    B-C 2
B-D 5    C-D 6    C-E 7
D-E 2    D-F 8    E-F 3

Démarrez en A. À chaque tour, la « frontière » est l'ensemble des arêtes ayant exactement une extrémité dans l'arbre, et l'algorithme prend la moins chère d'entre elles.

1. Arbre = {A}. Frontière : A-C (1), A-B (4). La moins chère est A-C (1). Ajoutez C.
2. Arbre = {A, C}. Frontière : B-C (2), A-B (4), C-D (6), C-E (7). Remarquez que B est désormais atteignable de deux façons, à 4 via A et à 2 via C, sa clé tombe donc à 2. La moins chère est B-C (2). Ajoutez B.
3. Arbre = {A, C, B}. Frontière : B-D (5), C-D (6), C-E (7). D est atteignable à 5 ou à 6, sa clé vaut donc 5. La moins chère est B-D (5). Ajoutez D.
4. Arbre = {A, C, B, D}. Frontière : D-E (2), C-E (7), D-F (8). La clé de E passe de 7 à 2. La moins chère est D-E (2). Ajoutez E.
5. Arbre = {A, C, B, D, E}. Frontière : E-F (3), D-F (8). La clé de F passe de 8 à 3. La moins chère est E-F (3). Ajoutez F.

Cinq arêtes ajoutées pour six sommets, et l'algorithme s'arrête. L'arbre est A-C (1), B-C (2), B-D (5), D-E (2), E-F (3), pour un poids total de 13. Les arêtes A-B (4), C-D (6), C-E (7) et D-F (8) ne servent jamais.

Deux moments de ce déroulé méritent qu'on s'y arrête. Au tour 3, l'algorithme a accepté une arête de poids 5 alors qu'une arête de poids 2 (D-E) restait intacte ailleurs dans le graphe. Prim ne peut pas encore prendre D-E car aucune de ses extrémités n'est dans l'arbre, et la prendre laisserait deux fragments disjoints au lieu d'un seul arbre en croissance. Au tour 4, la clé de E est tombée de 7 à 2 dès que D a rejoint l'arbre. Les clés ne peuvent que diminuer, et c'est ce qui rend efficace la mise en oeuvre par file de priorité.

5. Implémentation : Prim paresseux et Prim actif

Deux implémentations sont courantes, et la différence tient à ce que contient la file de priorité.

Prim paresseux

La version la plus simple pousse toutes les arêtes rencontrées dans un tas-min et écarte à l'extraction les entrées devenues obsolètes.

function LazyPrim(Graph, start):
    inTree = set()
    pq = tas-min vide, ordonné par poids d'arête
    mst = []

    visit(start)                    // marquer et empiler ses arêtes

    while pq non vide and size(mst) < V - 1:
        (w, u, v) = pq.pop()        // arête la moins chère vue
        if v in inTree: continue    // obsolète : deux bouts déjà dans l'arbre
        mst.append((u, v, w))
        visit(v)

    return mst

function visit(x):
    inTree.add(x)
    for chaque arête (x, y) de poids w:
        if y not in inTree: pq.push((w, x, y))

La ligne if v in inTree: continue fait le vrai travail. C'est elle qui empêche un cycle, et c'est pourquoi le tas peut contenir sans danger des entrées périmées : elles sont simplement ignorées lorsqu'elles remontent.

Prim actif

La version active conserve au plus une entrée par sommet, la key[v] courante, et l'abaisse sur place par une opération decrease-key. Elle exige une file de priorité indexée, donc plus de machinerie, mais le tas ne dépasse jamais V entrées au lieu de E.

function EagerPrim(Graph, start):
    for chaque sommet v:
        key[v] = Infinity
        parent[v] = Null
    key[start] = 0
    pq = tas-min indexé de tous les sommets, ordonné par key[]

    while pq non vide:
        u = pq.popMin()
        inTree.add(u)
        for chaque arête (u, v) de poids w:
            if v not in inTree and w < key[v]:
                key[v] = w                  // le POIDS de l'arête, pas une somme
                parent[v] = u
                pq.decreaseKey(v, w)

    return parent            // parent[] est l'arbre

Préférez Prim actif sur les graphes denses, où E dépasse largement V et où garder chaque arête dans le tas devient un gaspillage. Prim paresseux convient parfaitement aux graphes creux et se code juste bien plus facilement.

6. Complexité en temps et en espace

• Prim paresseux, tas binaire : O(E log E) en temps. Chaque arête peut être empilée et dépilée une fois. Comme E < V2, log E est en O(log V), d'où l'écriture habituelle O(E log V). Espace : O(E).
• Prim actif, tas binaire indexé : O(E log V) en temps, par V extractions et jusqu'à E opérations decrease-key, chacune en O(log V). Espace : O(V).
• Prim actif, sans tas, matrice d'adjacence : O(V2) en temps par recherche linéaire du minimum. Sur un graphe dense, où E approche V2, cela bat la version avec tas, car O(V2) vaut mieux que O(V2 log V).
• Prim actif, tas de Fibonacci : O(E + V log V), la meilleure borne connue pour Prim, puisque decrease-key devient à coût constant amorti. Les constantes sont assez grandes pour qu'il l'emporte rarement en pratique.

En résumé pratique : tas binaire sur les graphes creux, et simple balayage O(V2) sur matrice pour les denses. Le tas de Fibonacci relève surtout de l'intérêt théorique.

7. Prim contre Dijkstra : une ligne d'écart

Placez le pseudo-code de Prim actif à côté de l'algorithme de Dijkstra : ce sont presque les mêmes programmes. Tous deux gardent une clé par sommet, tous deux extraient le minimum à répétition, tous deux relâchent les voisins de ce qu'ils viennent d'extraire. Toute la différence tient à ce que l'on met dans la clé :

Prim :      if w < key[v]:              key[v] = w
Dijkstra :  if key[u] + w < key[v]:     key[v] = key[u] + w

La clé de Prim est le poids d'une seule arête. Celle de Dijkstra est la longueur cumulée d'un chemin entier depuis la source. Voilà pourquoi ils répondent à des questions différentes : Prim demande « quelle est la façon la moins chère de rattacher ce sommet à mon arbre », et Dijkstra demande « quelle est la façon la moins chère d'atteindre ce sommet depuis la source ».

Cela explique aussi pourquoi les poids négatifs cassent l'un et pas l'autre. La correction de Dijkstra repose sur le fait que les coûts de chemin ne diminuent jamais lorsque les chemins s'allongent, ce qu'une arête négative détruit. Prim n'additionne jamais de poids, si bien que les poids négatifs lui sont totalement inoffensifs. Un arbre couvrant de poids minimal est bien défini sur un graphe à poids négatifs, et Prim le trouve sans modification.

8. Prim contre Kruskal

Les deux algorithmes sont gloutons, tous deux se justifient par la propriété de coupe, et sur un graphe à poids distincts tous deux renvoient le même arbre. Ils diffèrent par ce qu'ils gardent connexe en chemin.

• Prim maintient à tout instant un seul arbre connexe et le fait croître vers l'extérieur. Il ne trie jamais les arêtes et exige une file de priorité.
• Kruskal trie toutes les arêtes par poids et ajoute chacune sauf si elle ferme un cycle, maintenant donc une forêt de fragments qui ne fusionnent en un arbre qu'à la toute fin. Il exige une structure union-find.

La règle pratique découle de la densité. Le coût de Kruskal est dominé par le tri, en O(E log E), excellent quand E est petit. Prim avec matrice d'adjacence tourne en O(V2) quel que soit le nombre d'arêtes, et l'emporte sur les graphes denses. Sur une entrée non connexe s'ajoute une différence structurelle : Kruskal produit naturellement une forêt couvrante de poids minimal, tandis que Prim, parti d'un unique sommet, ne couvre que la composante de ce sommet, ce qui oblige à le relancer une fois par composante.

9. Notes pratiques et pièges courants

Quatre situations font trébucher au passage du cas d'école aux données réelles.

• Des poids ex aequo signifient plusieurs réponses valides. Lorsque deux arêtes partagent un poids, le graphe peut posséder plus d'un arbre couvrant de poids minimal, et celui que vous obtenez dépend de la façon dont votre file de priorité départage. Tous sont également optimaux, si bien qu'un test comparant à une liste d'arêtes figée échouera sans raison. Comparez plutôt le poids total.
• Une entrée non connexe échoue en silence. Lancé depuis un sommet, Prim ne couvre que la composante de ce sommet puis s'arrête, en renvoyant un arbre qui paraît parfaitement valide. Le contrôle consiste à compter : un vrai arbre couvrant possède exactement V - 1 arêtes. Moins signifie que le graphe était non connexe et qu'il faut relancer depuis un sommet non visité.
• Boucles et arêtes multiples. Une boucle ne peut jamais traverser une coupe, elle est donc toujours ignorable. Parmi des arêtes multiples reliant la même paire de sommets, seule la moins chère peut être retenue. Ni l'une ni l'autre ne casse l'algorithme, mais les filtrer à la lecture garde le tas plus petit.
• Les graphes orientés sont un tout autre problème. Un arbre couvrant de poids minimal se définit pour des graphes non orientés. Donner des arêtes orientées à Prim produit quelque chose de dénué de sens. L'analogue orienté est une arborescence couvrante de poids minimal, obtenue par l'algorithme d'Edmonds, et elle est nettement plus difficile.

10. Applications concrètes

Les arbres couvrants de poids minimal répondent à une question récurrente : quelle est la façon la moins chère de tout relier, sans redondance ? Prim convient aux cas où le réseau croît réellement depuis une source.

Tracé de réseaux et de services

Poser du câble, de la fibre, une canalisation ou une route entre un ensemble fixe de sites, où chaque site doit être atteignable et où l'on minimise la longueur ou le coût total, est la motivation d'origine. L'article de Prim est né exactement de ce problème aux Bell Labs.

Analyse de regroupement

Construire l'arbre couvrant de poids minimal d'un nuage de points puis en supprimer les arêtes les plus lourdes, c'est le regroupement par lien simple : retirer les k - 1 arêtes les plus lourdes laisse exactement k groupes. L'arbre se calcule une fois et toute valeur de k en découle.

Approximation de problèmes plus durs

L'arbre couvrant de poids minimal fournit une borne inférieure pour la tournée du voyageur de commerce, et doubler ses arêtes donne une tournée au plus deux fois l'optimum sur les instances métriques. C'est le point de départ de la construction de Christofides, qui améliore cette garantie à 1,5.

Segmentation d'images et génération de labyrinthes

En traitant les pixels comme des sommets et la dissemblance comme un poids d'arête, la segmentation fondée sur l'arbre couvrant regroupe une image en régions. Lancez plutôt Prim sur une grille à poids aléatoires et vous obtenez un labyrinthe d'aspect uniforme, ce qui en fait un classique de la génération procédurale.

11. Ressources académiques et histoire

Comme plusieurs algorithmes de graphes classiques, celui-ci a été découvert plus d'une fois, et le nom qu'il porte n'est pas celui de la personne qui l'a trouvé en premier.

• Otakar Borůvka (1926) a posé et résolu le premier le problème de l'arbre couvrant de poids minimal, motivé par l'électrification de la Moravie rurale. Son algorithme est différent : il ajoute l'arête la moins chère issue de chaque fragment, par tours parallèles.
• Vojtěch Jarník (1930) a publié l'algorithme que nous appelons aujourd'hui celui de Prim, dans une lettre répondant à Borůvka. C'est pourquoi on le nomme aussi, à juste titre, algorithme de Jarník-Prim.
• Robert C. Prim (1957) l'a redécouvert indépendamment aux Bell Laboratories en étudiant le coût des réseaux de connexion, et c'est son article qui a touché un large public.
• Edsger W. Dijkstra (1959) l'a redécouvert une troisième fois, dans le court article même qui introduisait son algorithme de plus court chemin, ce qui n'a rien d'un hasard vu leur proximité.

Pour le récit de référence sur qui a trouvé quoi et quand, voyez l'histoire du problème par Graham et Hell. Pour un traitement rigoureux assorti de preuves complètes de la propriété de coupe et des deux algorithmes, la référence standard est Cormen, Leiserson, Rivest et Stein, Introduction to Algorithms, au chapitre consacré aux arbres couvrants de poids minimal. Ceux que la limite de complexité intéresse devraient regarder le résultat des tas de Fibonacci de Fredman et Tarjan ainsi que l'algorithme quasi linéaire de Chazelle. Les références complètes figurent à la fin de cet article.