L’algorithme de Prim sert à trouver un arbre couvrant minimum dans un graphe pondéré non orienté. En clair, il relie tous les sommets avec un coût total minimal, sans créer de cycle.
L’idée est très intuitive : on part d’un sommet, puis on agrandit progressivement l’arbre en choisissant à chaque étape l’arête la moins chère qui permet d’atteindre un nouveau sommet.
En Python, l’implémentation la plus pratique utilise une liste d’adjacence et une file de priorité avec heapq.
from heapq import heappop, heappush
def prim(graphe, depart):
visites = set()
arbre = []
cout_total = 0
file = [(0, depart, None)]
while file and len(visites) < len(graphe):
cout, sommet, parent = heappop(file)
if sommet in visites:
continue
visites.add(sommet)
if parent is not None:
arbre.append((parent, sommet, cout))
cout_total += cout
for voisin, poids in graphe[sommet]:
if voisin not in visites:
heappush(file, (poids, voisin, sommet))
if len(visites) != len(graphe):
raise ValueError("Le graphe n'est pas connexe")
return cout_total, arbre
Cette version renvoie le coût total et les arêtes sélectionnées dans l’arbre couvrant minimum.
La réponse courte
Utilisez Prim quand :
- le graphe est pondéré, non orienté et connexe ;
- vous voulez relier tous les sommets au coût minimal ;
- le graphe est déjà représenté sous forme de liste d’adjacence ;
- vous voulez faire grandir la solution depuis un sommet de départ.
Exemple complet :
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)],
}
cout, arbre = prim(graphe, "A")
print(cout)
print(arbre)
Résultat :
13
[('A', 'C', 2), ('C', 'B', 1), ('B', 'D', 5), ('D', 'E', 2), ('E', 'F', 3)]
Le coût total vaut 13, et l’arbre contient bien n - 1 arêtes pour n sommets.
Ce qu’est un arbre couvrant minimum
Un arbre couvrant minimum, souvent abrégé en MST pour Minimum Spanning Tree, est une structure qui respecte trois règles :
- elle relie tous les sommets du graphe ;
- elle ne contient aucun cycle ;
- elle minimise la somme des poids des arêtes choisies.
Exemple concret : imaginez des villes à relier par des câbles. Chaque câble a un coût. Vous voulez connecter toutes les villes, sans poser de câble inutile, avec le coût total le plus faible.
Prim répond exactement à ce type de problème.
Attention : Prim ne cherche pas le plus court chemin entre deux sommets. Pour cela, on utilise plutôt Dijkstra, Bellman-Ford ou Floyd-Warshall selon le contexte. Prim cherche un réseau global minimal qui couvre tous les sommets.
Comment fonctionne l’algorithme de Prim
Prim maintient deux ensembles :
- les sommets déjà dans l’arbre ;
- les arêtes candidates qui permettent de rejoindre un sommet encore absent.
À chaque étape :
- on prend l’arête candidate de plus petit poids ;
- si elle mène vers un sommet déjà visité, on l’ignore ;
- sinon, on ajoute ce sommet à l’arbre ;
- on ajoute ses nouvelles arêtes candidates dans la file de priorité.
Ce comportement ressemble à une extension progressive : l’arbre grandit depuis le départ, toujours par le choix local le moins cher disponible.
Représenter le graphe en Python
Une représentation simple est la liste d’adjacence.
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)],
}
Chaque clé est un sommet. Chaque valeur est une liste de couples :
(voisin, poids)
Comme le graphe est non orienté, chaque arête apparaît dans les deux sens :
"A": [("B", 4)]
"B": [("A", 4)]
Si vous oubliez un sens, l’algorithme peut produire un résultat incomplet ou dépendre du sommet de départ.
Pourquoi utiliser heapq
À chaque étape, Prim doit choisir l’arête candidate la moins chère. Une file de priorité est donc la bonne structure.
En Python, le module standard heapq fournit un tas binaire minimal. On y empile des tuples :
(poids, sommet, parent)
Python compare les tuples dans l’ordre. Le plus petit poids remonte donc en premier.
from heapq import heappop, heappush
file = []
heappush(file, (4, "B", "A"))
heappush(file, (2, "C", "A"))
print(heappop(file)) # (2, 'C', 'A')
Cette mécanique évite de trier toutes les arêtes candidates à chaque étape.
Implémentation complète de Prim avec heapq
Voici une version claire et robuste pour un graphe connexe.
from heapq import heappop, heappush
def prim(graphe, depart):
if depart not in graphe:
raise ValueError("Le sommet de départ n'existe pas")
visites = set()
arbre = []
cout_total = 0
file = [(0, depart, None)]
while file and len(visites) < len(graphe):
cout, sommet, parent = heappop(file)
if sommet in visites:
continue
visites.add(sommet)
if parent is not None:
arbre.append((parent, sommet, cout))
cout_total += cout
for voisin, poids in graphe[sommet]:
if voisin not in visites:
heappush(file, (poids, voisin, sommet))
if len(visites) != len(graphe):
raise ValueError("Le graphe n'est pas connexe")
return cout_total, arbre
Test :
cout, arbre = prim(graphe, "A")
print("Coût total :", cout)
for u, v, poids in arbre:
print(u, "-", v, ":", poids)
Résultat :
Coût total : 13
A - C : 2
C - B : 1
B - D : 5
D - E : 2
E - F : 3
L’ordre exact peut varier si plusieurs arêtes ont le même poids, mais le coût minimal doit rester correct.
Vérifier le résultat
Pour un graphe connexe avec n sommets, l’arbre couvrant minimum doit contenir exactement n - 1 arêtes.
cout, arbre = prim(graphe, "A")
assert len(arbre) == len(graphe) - 1
Vous pouvez aussi vérifier que tous les sommets apparaissent dans l’arbre :
def sommets_de_l_arbre(arbre, depart):
sommets = {depart}
for u, v, _ in arbre:
sommets.add(u)
sommets.add(v)
return sommets
cout, arbre = prim(graphe, "A")
print(sommets_de_l_arbre(arbre, "A") == set(graphe))
Ces vérifications sont utiles quand vous modifiez le graphe ou quand vous construisez les données depuis un fichier.
Complexité de l’algorithme
Avec une liste d’adjacence et heapq, la complexité est généralement notée :
O(E log E)
où :
Vest le nombre de sommets ;Eest le nombre d’arêtes.
On voit aussi souvent O(E log V) selon l’implémentation et la manière de gérer les mises à jour de priorité. En Python avec heapq, on empile souvent plusieurs entrées candidates et on ignore les sommets déjà visités au moment du heappop. Cette version est simple et efficace, mais elle peut contenir des doublons dans le tas.
La mémoire utilisée est en O(E) dans le pire cas, à cause des arêtes candidates stockées dans la file.
Pour un guide plus général sur ces notations, vous pouvez relire la complexité algorithmique en Python.
Graphe non connexe : arbre ou forêt couvrante ?
Prim part d’un sommet. Si le graphe n’est pas connexe, il ne peut couvrir que la composante qui contient ce sommet.
Exemple :
graphe_non_connexe = {
"A": [("B", 1)],
"B": [("A", 1)],
"C": [("D", 2)],
"D": [("C", 2)],
}
prim(graphe_non_connexe, "A")
La fonction précédente lève une erreur, car tous les sommets ne sont pas atteints.
Si vous voulez traiter un graphe non connexe, il faut construire une forêt couvrante minimum : un arbre minimum par composante.
def foret_prim(graphe):
visites_globales = set()
foret = []
cout_total = 0
for depart in graphe:
if depart in visites_globales:
continue
visites = set()
arbre = []
file = [(0, depart, None)]
while file:
cout, sommet, parent = heappop(file)
if sommet in visites:
continue
visites.add(sommet)
visites_globales.add(sommet)
if parent is not None:
arbre.append((parent, sommet, cout))
cout_total += cout
for voisin, poids in graphe[sommet]:
if voisin not in visites:
heappush(file, (poids, voisin, sommet))
foret.append(arbre)
return cout_total, foret
Cette variante ne renvoie pas un seul arbre, mais une liste d’arbres.
Prim ou Kruskal : lequel choisir ?
Prim et Kruskal résolvent le même problème, mais ils ne partent pas de la même représentation.
| Critère | Prim | Kruskal |
|---|---|---|
| Stratégie | Agrandit un arbre depuis un sommet | Trie les arêtes puis évite les cycles |
| Structure typique | File de priorité | Union-Find |
| Données naturelles | Liste d’adjacence | Liste d’arêtes |
| Graphe non connexe | Couvre une composante depuis le départ | Produit naturellement une forêt si on le laisse faire |
| Point fort | Très pratique avec heapq |
Très clair pour raisonner sur les cycles |
Si vos données sont déjà sous forme :
{"A": [("B", 4), ("C", 2)]}
Prim est naturel.
Si vos données sont déjà sous forme :
[("A", "B", 4), ("A", "C", 2)]
Kruskal peut être plus direct.
Pour une comparaison complète, voir Prim vs Kruskal en Python.
Utiliser NetworkX quand le projet devient sérieux
Pour apprendre, écrire Prim soi-même est excellent. Pour un projet réel, une bibliothèque de graphes peut être préférable.
Avec NetworkX, le calcul d’un arbre couvrant minimum est direct :
import networkx as nx
G = nx.Graph()
G.add_weighted_edges_from([
("A", "B", 4),
("A", "C", 2),
("B", "C", 1),
("B", "D", 5),
("C", "D", 8),
("C", "E", 10),
("D", "E", 2),
("D", "F", 6),
("E", "F", 3),
])
T = nx.minimum_spanning_tree(G, algorithm="prim")
print(T.edges(data=True))
NetworkX est pratique pour manipuler, analyser et visualiser des graphes. Mais comprendre Prim reste utile pour savoir ce que fait la bibliothèque.
Erreurs fréquentes
Confondre arbre couvrant minimum et plus court chemin
Prim ne répond pas à la question :
Quel est le chemin le moins cher entre A et F ?
Il répond plutôt à :
Comment relier tous les sommets avec le coût total minimal ?
Ce sont deux problèmes différents.
Utiliser Prim sur un graphe orienté sans adaptation
L’algorithme de Prim s’applique aux graphes non orientés. Si vos arêtes ont un sens, il faut vérifier que le problème correspond vraiment à un arbre couvrant minimum non orienté.
Oublier d’ajouter les arêtes dans les deux sens
Dans une liste d’adjacence pour un graphe non orienté, cette arête :
("A", "B", 4)
doit apparaître chez A et chez B.
Ne pas gérer les graphes non connexes
Si le graphe n’est pas connexe, il n’existe pas d’arbre couvrant qui relie tous les sommets. Il existe seulement une forêt couvrante, avec une composante par groupe de sommets.
Croire que le premier sommet change le coût minimal
Dans un graphe connexe, le sommet de départ peut changer l’ordre des arêtes sélectionnées, surtout en cas d’égalité, mais il ne doit pas changer le coût total minimal.
Exercices rapides
Exercice 1
Quel est le coût de l’arbre couvrant minimum ?
graphe = {
"A": [("B", 3), ("C", 1)],
"B": [("A", 3), ("C", 2), ("D", 4)],
"C": [("A", 1), ("B", 2), ("D", 5)],
"D": [("B", 4), ("C", 5)],
}
cout, arbre = prim(graphe, "A")
print(cout)
print(arbre)
Correction :
7
Une solution possible contient les arêtes A-C, C-B et B-D.
Exercice 2
Modifiez la fonction pour renvoyer seulement la liste des arêtes, sans le coût total.
Correction possible :
def prim_aretes(graphe, depart):
cout, arbre = prim(graphe, depart)
return arbre
Exercice 3
Que se passe-t-il si vous supprimez toutes les arêtes entre deux composantes ?
La fonction doit lever une erreur si elle attend un graphe connexe. Si vous voulez un résultat, utilisez une variante de forêt couvrante.
Pour aller plus loin
Prim est un bon algorithme à maîtriser parce qu’il relie plusieurs notions fondamentales : graphes pondérés, file de priorité, complexité, glouton, arbre couvrant minimum et choix de représentation des données.
Pour continuer dans le cluster graphes et algorithmique :
- Prim vs Kruskal en Python : choisir le bon algorithme de graphe
- Algorithmes de graphes en Python : le guide pour bien démarrer
- Complexité algorithmique en Python : comprendre O(n), O(log n) et O(n²)
La règle à retenir : Prim construit progressivement un arbre en choisissant toujours l’arête candidate la moins chère vers un nouveau sommet. En Python, heapq est l’outil standard pour rendre cette sélection efficace.
Références
- Documentation Python officielle :
heapq, file de priorité basée sur un tas - Documentation NetworkX :
minimum_spanning_tree - Documentation NetworkX : algorithmes d’arbres couvrants minimum
