Algorithme de Prim

Imaginez que vous posez des câbles depuis une centrale électrique : vous reliez d'abord la ville la plus proche, puis la ville la plus proche de n'importe quel point déjà relié, et ainsi de suite. C'est l'algorithme de Prim, et il finit toujours avec le réseau le moins cher possible.

Un graphe avec un arbre qui grandit depuis un nœud, les nœuds en attente autour avec leurs meilleures arêtes en pointillés, et la liste des nœuds en attente en dessous
Un graphe avec un arbre qui grandit depuis un nœud, les nœuds en attente autour avec leurs meilleures arêtes en pointillés, et la liste des nœuds en attente en dessous

L'idée

Un arbre couvrant minimal relie tous les nœuds d'un graphe pondéré avec la plus petite longueur totale d'arêtes possible. L'algorithme de Prim le construit en faisant grandir un seul arbre vers l'extérieur depuis un départ. L'arbre ne se coupe jamais en morceaux : à chaque étape, exactement un nouveau nœud le rejoint, par la plus courte arête qui sort de l'arbre.

Pas à pas

Placez le départ dans l'arbre. Pour chaque nœud hors de l'arbre, gardez sa meilleure arête : sa plus courte arête vers un nœud de l'arbre. Puis répétez : prenez le nœud extérieur dont la meilleure arête est la plus courte, ajoutez-le à l'arbre avec cette arête, et examinez ses arêtes. Un voisin hors de l'arbre qu'une arête plus courte permet maintenant d'atteindre prend cette arête comme nouvelle meilleure arête. Arrêtez quand tous les nœuds sont dans l'arbre.

Un exemple

Prenez les arêtes A–B de longueur 1, B–C 2, A–C 3, C–D 4 et B–D 5, et partez de A. Les arêtes de A donnent à B la meilleure arête 1 et à C la meilleure arête 3. B est le plus proche, il rejoint donc l'arbre par A–B ; ses arêtes améliorent C à 2 et donnent 5 à D. C rejoint l'arbre par B–C, et son arête C–D améliore D à 4. Enfin, D rejoint l'arbre par C–D. L'arbre A–B, B–C, C–D a une longueur totale de 1 + 2 + 4 = 7.

Pourquoi il est correct

À chaque étape, les nœuds sont séparés en deux groupes : ceux de l'arbre et ceux de l'extérieur. La propriété de la coupe dit que la plus courte arête entre deux tels groupes appartient toujours à un arbre couvrant minimal. Prim ajoute toujours exactement cette arête : l'arbre construit jusqu'ici peut donc toujours être complété en un arbre couvrant minimal, et quand tous les nœuds l'ont rejoint, il en est un.

Histoire et vitesse

Le mathématicien tchèque Vojtěch Jarník a publié l'algorithme en 1930. Robert Prim l'a redécouvert chez Bell Labs en 1957, et Edsger Dijkstra à nouveau en 1959. Avec les nœuds en attente dans un tas binaire, le travail croît en E log V pour V nœuds et E arêtes ; avec un simple tableau, il est d'environ V², ce qui est mieux quand presque toutes les paires de nœuds sont reliées. Avec un tas de Fibonacci, il est en E + V log V.

À vous d'essayer

Ouvrez l'application, cliquez sur un nœud pour partir de là, et appuyez sur Étape. Les nœuds de l'arbre sont verts, les nœuds en attente bleus, et la meilleure arête de chaque nœud en attente est tracée en pointillés. Les nœuds en attente sont listés sous le graphe avec la longueur de leur meilleure arête, la plus courte d'abord : le premier rejoint l'arbre ensuite. Partez de différents nœuds et voyez l'ordre changer alors que le total reste le même.

Questions fréquemment posées

Quelle est la différence entre l'algorithme de Prim et celui de Dijkstra ?

Tous deux font grandir une région depuis un départ à l'aide d'une file de priorité. Prim classe un nœud en attente selon la longueur de sa meilleure arête vers l'arbre ; Dijkstra selon sa distance entière depuis le départ. Prim donne un arbre couvrant minimal, Dijkstra un arbre de plus courts chemins.

L'algorithme de Prim marche-t-il avec des longueurs d'arêtes négatives ?

Oui. Contrairement à l'algorithme de Dijkstra, Prim ne fait que comparer des arêtes entre elles, donc les longueurs négatives ne posent aucun problème : il trouve quand même un arbre couvrant de plus petit total.

Et si le graphe n'est pas connexe ?

L'algorithme de Prim s'arrête alors dès qu'il a atteint tous les nœuds qu'il peut atteindre : il donne un arbre couvrant minimal du seul morceau qui contient le départ. Le relancer depuis un nœud pas encore atteint donne une forêt couvrante minimale.

Vaut-il mieux l'algorithme de Prim ou celui de Kruskal ?

Aucun ne gagne toujours. Prim convient aux graphes denses et aux graphes stockés sous forme de listes de voisins ; Kruskal aux graphes creux donnés sous forme de liste d'arêtes. Tous deux trouvent un arbre de même longueur totale.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer l'algorithme de Prim